91. Decode Ways

Decode Ways

Problem Description

A message containing letters  A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped and then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

 

Example 1:

Input: s = "12"
Output: 2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"
Output: 3

Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "06"
Output: 0

Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

Approach) Dynamic Programming

Ideas: 

Dynamic Programming

Example: '2223'

•  i = 0; 1 (the first character '2' has 1 decoding method)
•  i = 1; 2 (the first two characters '22' have 2 decoding methods)
•  i = 2; 3 (the first three characters '222' have 3 decoding methods)
•  i = 3; 5 (the first four characters '2223' have 5 decoding methods)

It is found that it conforms to the Fibonacci sequence, and the recursive formula is ways(n) = ways(n-1) + ways(n-2)

But this problem is difficult because there are many boundary problems, such as the number "2263", which does not conform to the above rules, because the last two digits "63" are not in the alphanumeric range.

Code:

/**
 * @param {string} s
 * @return {number}
 */

const numDecodings = (s) => {
  if (s[0] === '0') return 0
  
  const ways = new Array(s.length+1).fill(0).fill(1, 0, 2) // [1,1,0,0,.....]
  for (let i = 2; i <= s.length; i++) {
    let prevOne = Number(s[i-1]) // first character
    let prevTwo = Number(s[i-2])*10 + Number(s[i-1]) // first two characters
    if (1 <= prevOne && prevOne <= 9) ways[i] += ways[i-1]
    if (10 <= prevTwo && prevTwo <= 26) ways[i] += ways[i-2]
  }
  return ways[s.length]
}

Runtime: 80 ms, faster than 81.65% of JavaScript online submissions for Decode Ways.
Memory Usage: 42.2 MB, less than 82.90% of JavaScript online submissions for Decode Ways.

Complexity 

Time Complexity
Time complexity will be O(n).


Space Complexity
space complexity should also be O(n).

Top Down

const numDecodings = (s, cur = 0, dp = {}) => {
  if (dp[cur]) return dp[cur]; // Already processed so return
  if (s[cur] === '0') return 0; // Not valid, return 0
  if (cur >= s.length - 1) return 1; // Terminating case
  return (dp[cur] =
    numDecodings(s, cur + 1, dp) + // We process one char (that is not 0)
    (s[cur] + s[cur + 1] <= 26 ? numDecodings(s, cur + 2, dp) : 0)); // If it's a valid num <= 26, we process two chars
};

Bottom Up

const numDecodings = (s) => {
  const dp = Array(s.length + 1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= s.length; i++) {
    const one = Number(s.slice(i - 1, i)); // '0' to '9'
    const two = Number(s.slice(i - 2, i)); // '00' to '99'
    if (one !== 0) dp[i] += dp[i - 1]; // We want [1, 9]
    if (10 <= two && two <= 26) dp[i] += dp[i - 2]; // We want [10, 26]
  }
  return dp[s.length];
};

Approach) Recursive caching solution (DFS)

const numDecodings = (s) => {
  const dp = {  // cache i: 
    [s.length]: 1
  }
  
  const dfs = (i) => { // i is the position we are at in s
    if (i in dp) { // if i has already been cached or if it's the last position in our string
      return dp[i];
    }
    if (s[i] === '0') { // bad base case: if char is starting with 0 then it is invalid
      return 0;
    }
    
    let result = dfs(i + 1); // we take the char at i as a single digit

    if ( // if double-digit value between 10-26
      i + 1 < s.length && // if we do have a second char that comes after the first
      (
        s[i] === '1' || // if double-digit value starts with 1 and there is a second digit then we have a valid double-digit value that starts with 1 ex: 10 - 19
        ( // if double-digit value starts with 2 and there is a second digit from 0 - 6, then we have a valid double-digit value that is in the range of 20-26
          s[i] === '2' &&
          '0123456'.search(s[i + 1]) !== -1
        )
      )
    ) {
      result += dfs(i + 2); // add dfs of valid double-digit value to current result
    }
    
    dp[i] = result; // cache result
    return result;
  }
  return dfs(0); // returns result of how many ways can decode string starting at index 0
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem #91. Decode Ways

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!