Question

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

A message containing letters from 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 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).

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

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; // initiator, just make forloop flow working
            dp[length - 1] = s.charAt(length - 1) == '0' ? 0 : 1; // assumption is starting at i, so starting as 0 is not decodable

            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];
        }
    }
}

############

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int a = 0, b = 1, c = 0;
        for (int i = 1; i <= n; ++i) {
            c = 0;
            if (s.charAt(i - 1) != '0') {
                c += b;
            }
            if (i > 1 && s.charAt(i - 2) != '0'
                && ((s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0') <= 26) {
                c += a;
            }
            a = b;
            b = c;
        }
        return c;
    }
}

// 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:
    def numDecodings(self, s: str) -> int:
        if len(s) == 0:
            return 0

        length = len(s)
        dp = [0] * (length + 1) # dp[i] => at index i, its decode ways

        dp[length] = 1 # initiator, just make forloop flow working
        dp[length - 1] = 0 if s[length - 1] == '0' else 1 # assumption is starting at i, so starting as 0 is not decodable

        for i in range(length - 2, -1, -1):
            if s[i] == '0':
                continue
            tem = int(s[i:i + 2])

            if tem > 26:
                dp[i] = dp[i + 1]
            else:
                dp[i] = dp[i + 1] + dp[i + 2]
        return dp[0]

class Solution: # no dp array
    def numDecodings(self, s: str) -> int:
        n = len(s)
        # a: dp[i-2], b: dp[i-1], c: count for current index i
        a, b, c = 0, 1, 0
        for i in range(1, n + 1):
            c = 0
            if s[i - 1] != '0':
                c += b
            if i > 1 and s[i - 2] != '0' and (int(s[i - 2]) * 10 + int(s[i - 1]) <= 26):
                c += a
            a, b = b, c
        return c

##############

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1
        for i in range(1, n + 1):
            if s[i - 1] != '0':
                dp[i] += dp[i - 1]
            if i > 1 and s[i - 2] != '0' and (int(s[i - 2]) * 10 + int(s[i - 1]) <= 26):
                dp[i] += dp[i - 2]
        return dp[n]

############

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]

func numDecodings(s string) int {
	n := len(s)
	dp := make([]int, n+1)
	dp[0] = 1
	for i := 1; i <= n; i++ {
		if s[i-1] != '0' {
			dp[i] += dp[i-1]
		}
		if i > 1 && s[i-2] != '0' {
			if (s[i-2]-'0')*10+(s[i-1]-'0') <= 26 {
				dp[i] += dp[i-2]
			}
		}
	}
	return dp[n]
}

public class Solution {
    public int NumDecodings(string s) {
        if (s.Length == 0) return 0;
        
        var f0 = 1;
        var f1 = 1;
        var f2 = 1;
        for (var i = 0; i < s.Length; ++i)
        {
            f0 = f1;
            f1 = f2;
            f2 = 0;
            var two = i > 0 ? int.Parse(string.Format("{0}{1}", s[i - 1], s[i])) : 0;
            if (two >= 10 && two <= 26)
            {
               f2 += f0;  
            }
            if (s[i] != '0')
            {
                f2 += f1;
            }
        }
        return f2;
    }
}

91 - Decode Ways

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions