LeetCode - 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.

 

Solution:

public int numDecodings(String s) {
    if(s.isEmpty()) return 0;
    int n = s.length();
    int[] f = new int[n];
    f[0] = s.charAt(0) !='0' ? 1 : 0;
    
    for(int i=1; i<n; i++) {
        if(s.charAt(i) !='0'){
            f[i] += f[i-1];
        }
        int str = Integer.parseInt(s.substring(i-1, i+1));
        if(str >=10 && str <=26) {
            f[i] += i>1?f[i-2]:1;
        }
    }
    
    return f[n-1];
}

  

又重新做了一遍这题，重构了一下代码：

public int numDecodings(String s) {
    int n = s.length();
    if(n == 0) return 0; // empty string has 0 decoding way.
    int[] f = new int[n+1];
    f[0] = 1;
    f[1] = s.charAt(0) == '0' ? 0 : 1;
    for(int i=2; i<=n; i++) {
        char c = s.charAt(i-1);
        if(c != '0') {
            f[i] += f[i-1];
        }
        int num = Integer.parseInt(s.substring(i-2, i));
        if(num >= 10 && num <= 26) {
            f[i] += f[i-2];
        }
    }
    return f[n];
} 

 

分享个简洁的C++代码：

int numDecodings(string s) {
    int n = s.size();
    if(!n || s[0]=='0') return 0;
    int f[n+1] = {1,1};
    for(int i=2; i<=n; i++) {
        if(s[i-1] != '0') {
            f[i] = f[i-1];
        }
        int val = stoi(s.substr(i-2,2));
        if(val>=10 && val<=26) {
            f[i] += f[i-2];
        }
    }
    return f[n];
}