Question

Formatted question description: https://leetcode.ca/all/91.html

91	Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

@tag-dp

Algorithm

Create a one-dimensional dp array, where dp[i] represents the number of decoding methods for the substring composed of the first i characters in s. The length is one more than the input array, and dp[0] is initialized to 1.

Now let’s look for the state transition equation. The value of dp[i] is inextricably linked to the previous state. Let’s analyze the example 226.

  • When i=1, the corresponding character in s is s[0]='2', there is only one split method, which is 2.
    • Note that s[0] must not be 0, otherwise it cannot be split.
  • When i=2, the corresponding character in s is s[1]='2'. Since s[1] is not 0, it can be split separately, which can be in the previous dp[i-1]
    • In each case, a single 2 is added, so that dp[i] can have at least as many splits as dp[i-1].

Next, it depends on whether it can be combined with the previous number. If the two digits are less than or equal to 26 and greater than or equal to 10 (because the high digit of the two digits cannot be 0), then you can add this two digit in each case of dp[i-2].

So In the end, dp[i] = dp[i-1] + dp[i-2], is it found to be consistent with the nature of the Fibonacci sequence? Therefore, 0 is a very special existence. If the current position is 0, it must not be separated separately, that is, dp[i-1] cannot be added, and it can only be seen whether the previous number is greater than or equal to 10 and less than or equal to 26, you can add dp[i-2] if you can, otherwise it can only be kept at 0.

The specific operation steps are, in the process of traversal, first check whether each number is 0, if so, assign dp[i] to 0, if not, assign the value of dp[i-1], and then see Whether the previous digit of the array exists, if it exists and meets that the previous digit is 1, or the two digits formed by the current digit are not greater than 26, then the current dp[i] value is added to dp[i-2]. Finally returns the last value of the dp array.

F(n) = F(n-1) + F(n-2)     		
* if s[n] is a valid encoding digit and s[n-1]s[n] is also a valid encoding number.

F(n) = F(n-1)                   
* if s[n] is a valid encoding digit and s[n-1]s[n] is NOT a valid encoding number.

F(n) = F(n-2)                   
* if s[n] is NOT a valid encoding digit and s[n-1]s[n] is  a valid encoding number.

F(n) = 0                        
* if s[n] is NOT a valid encoding digit and s[n-1]s[n] is NOT  a valid encoding number.

Code

Java

  • 
    public class Decode_Ways {
    
        public static void main(String[] args) {
            Decode_Ways out = new Decode_Ways();
            Solution_fromStart s = out.new Solution_fromStart();
    
            System.out.println(s.numDecodings("123"));
        }
    
    
        public class Solution {
            public int numDecodings(String s) {
    
                if(s.length() == 0) return 0;
    
                int length = s.length();
                int[] dp = new int[length + 1]; // dp[i] => at index i, its decode ways
    
                dp[length] = 1; // 初始值,启动值很重要,1 就是默认有一种解码方式
                dp[length - 1] = s.charAt(length - 1) == '0' ? 0 : 1;
    
                for(int i = length - 2; i >= 0; i--){
                    if(s.charAt(i) == '0') continue;
                    int tem = Integer.valueOf(s.substring(i,i + 2));
    
                    if(tem > 26){
                        dp[i] = dp[i + 1];
                    }else{
                        dp[i] = dp[i + 1] + dp[i + 2];
                    }
                }
                return dp[0];
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/decode-ways
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
      int numDecodings(string s) {
        int pre2 = 0, pre1 = 1;
        for (int i = 0; i < s.size() && pre1; ++i) {
          int cur = 0;
          if (s[i] != '0') cur += pre1;
          if (i != 0 && s[i - 1] != '0' && (s[i - 1] - '0') * 10 + s[i] - '0' <= 26)
            cur += pre2;
          pre2 = pre1;
          pre1 = cur;
        }
        return pre1;
      }
    };
    
  • class Solution(object):
      def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
          return 0
        dp = [0] * (len(s) + 1)
        dp[0] = 1
        dp[1] = 0 if s[0] == "0" else 1
        for i in range(1, len(s)):
          pre = int(s[i - 1])
          cur = int(s[i])
          num = pre * 10 + cur
          if cur != 0:
            dp[i + 1] += dp[i]
          if pre != 0 and 0 < num <= 26:
            dp[i + 1] += dp[i - 1]
    
        return dp[-1]
    
    

All Problems

All Solutions