🌗 91. 解码方法

难度: 🌗

问题描述

---

解法

class Solution {
    public int numDecodings(String s) {
        // 思路：
        // dp
        int len = s.length();
        int[] dp = new int[len + 1];
        dp[0] = 1;
        for(int i = 1; i <= len; i ++) {
            int m = i - 1;
            if(isValid(s, m, m)) {
                dp[i] += dp[i - 1]; // 单独成词
            }
            if(isValid(s, m - 1, m)) {
                dp[i] += dp[i - 2]; // 和前面的单词成词
            }
        }
        return dp[len];
    }

    private boolean isValid(String s, int left, int right) {
        int len = s.length();
        if(left < 0 || right >= len) {
            return false;
        }
        char high = s.charAt(left);
        char low = s.charAt(right);
        if(high == '1' && (low >= '0' && low <= '9')) {
            return true;
        }
        if(high == '2' && (low >= '0' && low <= '6')) {
            return true;
        }
        if(left == right && high >= '1' && high <= '9') {
            return true;
        }
        return false;
    }
}

---

输出