Leetcod 639. Decode Ways II

Posted on | In |

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

‘A’ -> 1

‘B’ -> 2

…

‘Z’ -> 26

Beyond that, now the encoded string can also contain the character ‘*’, which can be treated as one of the numbers from 1 to 9.

Given the encoded message containing digits and the character ‘*’, return the total number of ways to decode it.

Also, since the answer may be very large, you should return the output mod 109 + 7.

Example 1:

Input: “*”

Output: 9

Explanation: The encoded message can be decoded to the string: “A”, “B”, “C”, “D”, “E”, “F”, “G”, “H”, “I”.

Example 2:

Input: “1*”
Output: 9 + 9 = 18

动态规划

法一

递推
表达式

image

1
2


class Solution {
public:
const static int kMod=1000000007;
int numDecodings(string s) {
long dp[2]={1,ways(s[0])};
for(int i=1;i<s.length();i++){
long dp_i=dp[1]ways(s[i])+dp[0]ways(s[i-1],s[i]);
dp_i%=kMod;
dp[0]=dp[1];
dp[1]=dp_i;
}
return dp[1];
}

int ways(char s){
    if(s=='0') return 0;
    if(s=='*') return 9;
    if(s>='1'&&s<='9') return 1;
    else return 0;
}
int ways(char a,char b){
    if(a=='*'&&b=='*') return 15;
    else if(a=='*'){
        if('b'>='0'&&b<='6') return 2;
        else return 1;
    }
    else if(b=='*'){
        if(a=='1') return 9;
        else if(a=='2') return 6;
        else return 0;

  }
    else{
        int prefix=(a-'0')*10+b-'0';
        return prefix>=10&&prefix<=26;
    }


}

};

1
2
3
4
5
6
7
8
9






## 法二
数据规模很大
 递归 导致栈溢出 这种方法不可取

class Solution {
public:
const static int kMod=1000000007;
int numDecodings(string s) {
int i=s.length()-1;
if(s.length()==2) return ways(s[0],s[1])+ways(s[0])ways(s[1]);
else return decoding(s,i);
}
long decoding(string s,int i){
long ways_i=1;
if(i==-1) return 1;
if(i==0) return ways(s[0])%kMod;
ways_i=(ways(s[i])decoding(s,i-1)+ways(s[i-1],s[i])*decoding(s,i-2))%kMod;
return ways_i;

}
int ways(char s){
    if(s=='0') return 0;
    if(s=='*') return 9;
    if(s>='1'&&s<='9') return 1;
    else return 0;
}
int ways(char a,char b){
    if(a=='*'&&b=='*') return 15;
    else if(a=='*'){
        if('b'>='0'&&b<='6') return 2;
        else return 1;
    }
    else if(b=='*'){
        if(a=='1') return 9;
        else if(a=='2') return 6;
        else return 0;

  }
    else{
        int prefix=(a-'0')*10+b-'0';
        return prefix>=10&&prefix<=26;
    }


}

};
`

image