leetcode91-解码方法

解码方法

• dp

1. 如果当前位置的字符串不等于0，则表明这个字符可以被解码成新字符，dp[i] += dp[i-1]
2. 如果上一个位置的字符串等于1或者2并且与当前字符拼接的数字小于等于26，则表明本字符可以是上一个字符遗留下来的，dp[i] += dp[i-2]

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