grid47 Exploring patterns and algorithms
Oct 28, 2024
6 min read
Solution to LeetCode 91: Decode Ways Problem
You have intercepted a string of numbers that encodes a message. The message is decoded using the following mapping:
“1” -> ‘A’,
“2” -> ‘B’,
…
“26” -> ‘Z’.
However, there are multiple ways to decode the string, as some numbers can represent a single letter (e.g., ‘1’ for ‘A’, ‘12’ for ‘L’). Your task is to return the number of possible ways to decode the string. Note that strings containing invalid encodings (e.g., starting with zero or having codes larger than 26) should not be considered valid.
Problem
Approach
Steps
Complexity
Input: The input is a string s consisting only of digits, representing the encoded message.
Example: Input: s = "1234"
Constraints:
• 1 <= s.length <= 100
• s contains only digits
Output: The output is an integer, representing the number of valid ways to decode the string.
Example: Output: 3
Constraints:
• The output should fit within a 32-bit integer.
Goal: The goal is to count the number of ways the string can be decoded, by considering all possible valid groupings of numbers into letters and ensuring no invalid decodings (such as those starting with 0).
Steps:
• Check if the first character is '0', which would make the string invalid.
• Use dynamic programming or memoization to store the number of ways to decode the string from each position.
• At each step, consider both single-digit and two-digit numbers (if valid), and recursively calculate the number of decodings for the remaining substring.
Goal: The input string must only contain digits. Strings that start with '0' or have invalid groupings (e.g., '30') should return 0.
Steps:
• The string should contain only digits.
• The number of decodings should not exceed the maximum value of a 32-bit integer.
Assumptions:
• The input string is guaranteed to be non-empty and contain only digits.
• Input: Input: s = "1234"
• Explanation: "1234" can be decoded in three ways: as 'ABCD' (1 2 3 4), 'LCD' (12 3 4), or 'AWD' (1 23 4).
• Input: Input: s = "226"
• Explanation: "226" can be decoded as: 'BBF' (2 2 6), 'VF' (22 6), or 'BZ' (2 26).
• Input: Input: s = "06"
• Explanation: "06" cannot be decoded because '06' is not a valid encoding, so the output is 0.
Approach: We can solve this problem using dynamic programming. We will keep track of the number of ways to decode the string up to each position, considering both single-digit and two-digit numbers where valid.
Observations:
• This problem can be solved using dynamic programming or memoization to store intermediate results and avoid recalculating the same subproblems.
• The key observation is that valid encodings are formed by single digits ('1' to '9') and valid two-digit combinations ('10' to '26').
• The presence of '0' as a standalone digit or paired with another number (e.g., '10') requires careful handling to avoid invalid decodings.
Steps:
• Initialize a memoization array or use dynamic programming to store the number of ways to decode the string at each index.
• Iterate through the string, checking if each character or pair of characters forms a valid decoding.
• If the current character forms a valid digit (i.e., '1' to '9'), add the number of ways to decode the remaining string.
• If a pair of characters forms a valid two-digit number ('10' to '26'), add the number of ways to decode the remaining string.
Empty Inputs:
• An empty input string should return 0, as there are no ways to decode an empty string.
Large Inputs:
• For large input strings, the solution should still be efficient and handle up to 100 characters.
Special Values:
• Strings that start with '0' or contain invalid two-digit combinations (e.g., '30', '40') should return 0.
Constraints:
• Ensure that the solution works within the given constraint of a string length of up to 100 characters.
intnumDecodings(string s) {
if (s.empty() || s[0] =='0') return0;
vector<int> dp(s.size() +1, 0);
dp[0] =1;
dp[1] = s[0] =='0'?0:1;
for (int i =2; i <= s.size(); i++) {
int one_digit = stoi(s.substr(i -1, 1));
int two_digit = stoi(s.substr(i -2, 2));
if (one_digit >=1) {
dp[i] += dp[i -1];
}
if (two_digit >=10&& two_digit <=26) {
dp[i] += dp[i -2];
}
}
return dp[s.size()];
}
1 : Function Declaration
intnumDecodings(string s) {
Declares a function `numDecodings` that takes a string `s` of digits as input and returns the number of ways to decode it.
2 : Edge Case Check
if (s.empty() || s[0] =='0') return0;
Checks for edge cases: if the string is empty or starts with '0', there are no valid decodings.
3 : Array Initialization
vector<int> dp(s.size() +1, 0);
Initializes a dynamic programming array `dp` of size `s.size() + 1` to store the number of decodings for substrings ending at each index.
4 : Base Case Initialization
dp[0] =1;
Sets the base case: there is one way to decode an empty string.
5 : Base Case Initialization
dp[1] = s[0] =='0'?0:1;
Sets the base case for the first character: if it's '0', there are no decodings; otherwise, there's one.
6 : Loop Iteration
for (int i =2; i <= s.size(); i++) {
Iterates through the string, starting from the second character.
7 : Substring Extraction, String to Integer Conversion
int one_digit = stoi(s.substr(i -1, 1));
Extracts the current digit and converts it to an integer.
8 : Substring Extraction, String to Integer Conversion
int two_digit = stoi(s.substr(i -2, 2));
Extracts the two-digit number formed by the current and previous digits and converts it to an integer.
9 : Conditional Update
if (one_digit >=1) {
dp[i] += dp[i -1];
}
If the current digit is valid (1-9), adds the number of decodings for the substring ending at the previous index to the current `dp[i]`. This corresponds to decoding the current digit as a single-digit letter.
If the two-digit number is valid (10-26), adds the number of decodings for the substring ending at the index two positions before to the current `dp[i]`. This corresponds to decoding the current two digits as a single letter.
11 : Return
return dp[s.size()];
Returns the final value in the `dp` array, which represents the total number of decodings for the entire string.
Best Case: O(n), where n is the length of the input string.
Average Case: O(n)
Worst Case: O(n), since we only need to process each character of the string once.
Description: The time complexity is linear because each character is processed once.
Best Case: O(1), if no storage is required.
Worst Case: O(n), where n is the length of the input string, for storing the dynamic programming or memoization array.
Description: The space complexity is linear due to the storage requirements for the dynamic programming array.
