0091. 解码方法 [Medium] [Decode Ways].md

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 a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

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

Example 2:

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

---

题目：给定一个只有数字组成的字符串s，其中字符0实际代表的信息是A，1代表的是B,....,26代表的是Z。通过对字符串s进行合理的分隔，计算总共有多少种不同的方式去解码该字符串。

思路：回溯法，同LeetCode93. Restore IP Addresses， 但是[Time Limit Exceeded]。递归的深度是不确定的，用start表示每层递归的子字符串tmp的起始位置，i表示子字符串tmp的终止位置，然后判断不同长度下的tmp是否满足条件。进入下一层递归时，从s[i+1]的位置开始分隔。当start能够到达s的最后一个位置，说明已经找到了一种解码方式，回溯。

工程代码下载

class Solution {
public:
    int numDecodings(string s) {
        if(s == "") return 0;
        int res = 0;
        backtracking(s, res, 0);
        return res;
    }
private:
    void backtracking(string &s, int &res, int start){
        if(start == s.size()){
            ++res;
            return;
        }

        for(int i=start; i<s.size(); ++i){
            int length = i - start + 1;
            string tmp = s.substr(start, length);
            if(length > 2 || stoi(tmp) > 26 || stoi(tmp) == 0)
                break;
            backtracking(s, res, i + 1);
        }
    }
};

思路2：动态规划，参考DP Solution (Java) for reference。

if the last char of the String is '0'. it means there is no way to use it alone as a code. it has to be a part of another code. If the last char is not '0', let's say it's '5', the there is 1 way to use this number as a code. Link

doing dp from tail to head. memo[i] means ways of decoding for substring(i, end). at a certain point i, if the char is '0' then it must be combine with char i-1. Link

I am trying to add some notes to the code to make everybody understand better. Take manky's code as example. Assigning memo[n] = 1; means when the string is empty, there is only one answer. memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0; means when there is only one character in the string, if this character is not 0, there will be an answer, or there will be no answer. Then it starts the dp portion. When we add a letter from the end of the string, if the first two letters <=26, we can get memo[n]=memo[n+1]+memo[n+2]. For example, the String now is "123xxxx" and we know all the result from 2. Because 12<26, we can make this string either "12"+"3xxxx" or 1+23xxxx which is exactly memo[n]=memo[n-1]+memo[n-2]. if the String is"32xxxx" memo[n]=memo[n+1]. if there are 0s in the string, we should skip it and look at the next character because there is no answer when the string begins with 0. Link

用memo[i]表示子串substring(i, end)所有不同解码的数量。对于状态转移方程，假设已经确定了s[i+1,...end]子字符串的解码数量，那么对于第i个字符s[i]，如果s[i]=0，因为不能以0开头，memo[i]=0；如果s[i] != 0判断s[i,i+1]的十进制数值是否小于等于26，如果是，那么可以将s[i,...end]分为s[i,i+1]+s[i+2,...end]或者s[i]+s[i+1,...end]，如果s[i,i+1] > 26，只能将s[i,...end]分为s[i]+s[i+1,...end]，状态转移方程为memo[n]=memo[n+1] + memo[n+2], if s[n]!=0 && s[n,n+1]<=26, memo[n]=memo[n+1], if s[n]!=0 && s[n,n+1]>26.

class Solution {
public:
    int numDecodings(string s) {
        if(s == "") return 0;
        int n = s.size();
        vector<int> dp(n+1);
        dp[n] = 1;
        dp[n-1] = s[n-1] == '0' ? 0 : 1;
        for(int i = n-2; i>=0; --i){
            if(s[i] == '0')
                dp[i] = 0;
            else
                dp[i] = stoi(s.substr(i, 2)) <= 26 ?
                    dp[i+1] + dp[i+2] : dp[i+1];
        }
        return dp[0];
    }
};