力扣 91 解码方法

题意：给定一个字符串，里边是0-9的字符，数字的组合解码成a-z，求它的所有解码组合

思路：设一个dp数组，来记录当前index的组合数，设一个pre来记录上一个遍历到的数

1. 当当前数是0，如果上一个数不是1和2，那么数组违法，返回0，否则dp[i] = dp[i－2]，因为i-1和i只能和在一起组成“10”或“20”
2. 当pre是1时，那么dp[i] = dp[i-1]+dp[i-2]，因为当前数即可以自己算一个字符，也可以和1一起组成一个字符
3. 当pre时2时，
   如果cur是1-6，那么dp[i] = dp[i-1]+dp[i-2]，因为当前数即可以自己算一个字符，也可以和1一起组成一个字符
   否则 dp[i] = dp[i-1]，因为当前数只能自己算一个字符
4. 对于其他情况dp[i] = dp[i-1]，因为当前数只能自己算一个字符

思想：动态规划

复杂度：时间O（n)，空间O(n)

class Solution {
    public int numDecodings(String s) {
        int len = s.length();
        if(len == 0)
            return 0;
        int[] dp = new int[len+1];
        int pre = 0;
        dp[0] = 1;
        for(int i=1;i<=len;i++) {
            int cur = s.charAt(i-1) - '0';
            if(cur == 0) {
                if(pre != 1 && pre != 2) {
                    return 0;
                }
                dp[i] = dp[i-2];
            } else if(pre == 1) {
                dp[i] = dp[i-1] + dp[i-2];
            } else if(pre == 2) {
                if(cur>=1&&cur<=6)
                    dp[i] = dp[i-1] + dp[i-2];
                else 
                    dp[i] = dp[i-1];
            } else {
                dp[i] = dp[i-1];
            }
            pre = cur;
        }
        return dp[len];
    }
}