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.

 

public class Solution {
    // dp[i] = '0' < s.char(i) <= '9' ? d[i - 1] : 0
    //       + 9 < s.sub(i - 2, i) <= 26 ? d[i - 2] : 0
     public int numDecodings(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int N = s.length();
        int[] dp = new int[N + 1];
        dp[0] = 1; // 注意这个初始化条件
        dp[1] = (s.charAt(0) >= '1' && s.charAt(0) <= '9') ? 1 : 0;
        for (int i = 2; i <= N; i++) {
            char c = s.charAt(i - 1);
            if (c >= '1' && c <= '9')
                dp[i] = dp[i - 1];
            int prev2 = Integer.valueOf(s.substring(i-2, i));
            if (prev2 > 9 && prev2 < 27)
                dp[i] += dp[i - 2];
        }
        return dp[N];
     }
    
    /*Time Limit Exceeded O(N^3)
    public int numDecodings(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int N = s.length();
        int[][] dp = new int[N + 1][N + 1];
        
        // initialization dp[i][i+1]
        for (int i = 0; i < N; i++) {
            char c = s.charAt(i);
            dp[i][i + 1] = (c >= '1' && c <= '9') ? 1 : 0;
        }
        for (int i = 0; i < N - 1; i++) {
            String sub = s.substring(i, i + 2);
            dp[i][i + 2] = (sub.compareTo("10") >= 0 && sub.compareTo("27") < 0) ? 1 : 0;
        }
        for (int k = 3; k <= N; k++) {
            for (int i = 0; i <= N - k ; i++) {
                for (int j = i + 1; j <= i + k - 1; j++) {
                    dp[i][i + k] += dp[i][j] * dp[j][i + k];
                }
            }
        }
        return dp[0][N];
    }
    */
}

 

 

 

评论

2 楼 likesky3 2015-04-16  

递推公式代码注释中给出了。超时的那个解法多出了许多不必要的计算，题目只要求s(0,N)的译码种类，我却把s所有子串的译码种类都计算了，画蛇添足。做题要明确题意，求什么解什么。

1 楼 qb_2008 2015-04-15  

似乎我们要先尝试能否从一头推到另一头，即采用一维DP。递推公式大概是dp[i] = {dp[j]和s[i-j]的组合}。