091. Decode-Ways

difficulty: Medium

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

Method One

class Solution {
    public int numDecodings(String s) {
        // 这个和之前的一样，主要是思想转不过来
        // 对于第 N 个字符，想要到达它，只能通过第 N - 1 和 第 N - 2 个字符。
        // 若通过 N - 1 到达 N ，解码方式只能把 N 单独解码。那么 dp[N] 加上 dp[N - 1];
        // 若通过 N - 2 到达 N ，解码方式只能把 N 和 N - 1 一起解码，那么 dp[N] 再加上 dp[N - 2];
        // 比如 987654321，到达1，可以通过 98765432，也可以通过 9876543 
        // 这个题还有0就比较恶心。因为如果有单独的 0，例如 909，那么总数直接是0.
        // 但是如果0可以和10 20 结合，那么 像 1020101 就可以有结合的方式，总数并不是0。
​
        //这个方法是最省空间的，但是处理edge cases 就很棘手。
        if(s.length() < 1) {
            return 0;
        }
​
        int prev2 = 1; // 第 1 个，作为辅助开始
        int prev  = s.charAt(0) == '0' ? 0:1; // 真实的第一个
        if(s.length() < 2) {
            return prev;
        }
        
        int cur = 0;
        for(int i = 1 ; i < s.length() ; i++ ) {
            int one = Integer.parseInt( s.substring(i, i + 1) );
            int two = Integer.parseInt( s.substring(i - 1, i + 1) );
            if( one == 0 ) {
                cur = 0;
            }
            if( one > 0 ) {
                cur = prev;
            }
            if( two > 9 && two < 27) {
                cur += prev2;
            }
            
            prev2 = prev;
            prev = cur;
        }
        return cur;        
    }
}
​

2022年写的，确实是好了很多啊。

class Solution {
    public int numDecodings(String s) {
        // substr(size - 1, size);
        // substr(size - 2, size);
        // int[] dp = new int[s.length + 1];
        int prevPrevWays = 0;
        int prevWays = 1;
        for(int i = 1; i <= s.length(); i++){
            int curWays = 0;
            if(isValid(s.substring(i - 1, i))){
                curWays += prevWays;
            }
            if(i > 1 && isValid(s.substring(i - 2, i))){
                curWays += prevPrevWays;
            }
            prevPrevWays = prevWays;
            prevWays = curWays;
        }
        return prevWays;
    }

    private boolean isValid(String s){
        int parsedInt = Integer.parseInt(s);
        if(parsedInt > 0 && parsedInt < 10 && !s.startsWith("0")){
            return true;
        }
        if(parsedInt >= 10 && parsedInt <= 26){
            return true;
        }
        return false;
    }
}

2023 年写的:

class Solution {
    public int numDecodings(String s) {
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                dp[i + 1] = 0;
            } else {
                dp[i + 1] = dp[i];
            }
            if (i == 0) continue;
            int parsedInt = Integer.parseInt(s.substring(i - 1, i + 1));
            if (parsedInt <= 26 && parsedInt >= 10) {
                dp[i + 1] += dp[i - 1];
            }
        }
        return dp[s.length()];
    }
}

或者这样, 差不多。可以继续优化节省的那点空间意义不大。

class Solution {
    public int numDecodings(String s) {
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '0') {
                dp[i + 1] = dp[i];
            }
            if (i == 0) continue;
            int parsedInt = Integer.parseInt(s.substring(i - 1, i + 1));
            if (parsedInt <= 26 && parsedInt >= 10) {
                dp[i + 1] += dp[i - 1];
            }
        }
        return dp[s.length()];
    }
}