Leetcode/F家微软 -- 91. Decode Ways(DP)

91. Decode Ways(DP)
medium
https://leetcode.com/problems/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.

 Microsoft Uber Facebook

思路： use dp to add through string. Prefill dp[0] 1. For  current char,
1 - If cur.val != 0, dp[i+1](cur) = dp[i](pre) - inherit last char (we treat cur as one letter)
2 - If cur.val + pre.val * 10 in [10,26], dp[i+1] += dp[i-1] - add 2nd last char(we treat cur&last as one letter)
Complexity: Time O(n) Space O(n)

//invalid case: 001, 1001 ..., return 0
    public int numDecodings(String s) {
        if(s.length() == 0||s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length() + 1];//need prefill 2 val in dp
        dp[0] = 1;//default val
        dp[1] = 1;//filled by 1st char in s
        for(int i = 1; i < s.length(); i++){
            int pre = s.charAt(i-1) - '0';
            int cur = s.charAt(i) - '0';
            if(cur != 0){//no char for single 0
                dp[i+1] = dp[i];
            }
            int sum = pre*10 + cur;
            if(sum >= 10 && sum <=26){//eg:01 not valid, only bt [10,26]
                dp[i+1] += dp[i-1];
            }
        }
        return dp[dp.length - 1];
    }

/*125  127
  ABE   ABG 
   LE    LG
   AY   
----------
   3     2 
*/