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

Solution

dp or memorization

过程:
1. define OPT(i)
2. Find recursive relation
OPT(i) =
OPT(i + 1)
OPT(i + 2) if s[i, i+2] is valid
3. Initialization
OPT(s.length()) = 1
OPT(s.length() - 1) = 1 if it is valid

注意点:
1. edge case,防止数组越界

Complexity

O(N) O(N)

Code

    class Solution {
        public int numDecodings(String s) {
            if(s == null || s.length() == 0)
                return 0;
            int[] dp = new int[s.length() + 1];
            dp[s.length()] = 1;
            char last = s.charAt(s.length() - 1);
            if(last >= '1' && last <= '9')
                dp[s.length() - 1] = 1;

            for(int i = s.length() - 2; i >= 0; i--){
                if(s.charAt(i) == '0' )
                    continue;
                dp[i] += dp[i+1];
                int tmp = Integer.parseInt(s.substring(i,i+2));
                if(tmp >= 1 && tmp <= 26){
                    dp[i] += dp[i + 2];
                }
            }
            return dp[0];
        }
    }