[leetcode #91] Decode Ways

Problem
A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106"can be mapped into:

・ "AAJF" with the grouping (1 1 10 6)
・ "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06"cannot be mapped into 'F' since "6"is different from "06".
Given a string s containing only digits, return the number of ways to decode it.
The answer is guaranteed to fit in a 32-bit integer.
Example 1:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "0"
Output: 0
Explanation: There is no character that is mapped to a number starting with 0.
The only valid mappings with 0 are 'J' -> "10" and 'T' -> "20", neither of which start with 0.
Hence, there are no valid ways to decode this since all digits need to be mapped.

Example 4:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

Constraints:

・ 1 <= s.length <= 100
・ s contains only digits and may contain leading zero(s).

Idea
以前にDecodeWaysIIを解いたことがあるので、簡単に解けました.アルファベット順で1～26を一致させることができますが、数値で符号化された文字列をアルファベットに再変換する場合、可能なアルファベット文字列の数はどれくらいかが問題です.注意すべき点は0と2桁の数字を処理することです.
前から文字列を検索し、その文字列の復号可能な数字をdpに格納します.現在検索中の文字のインデックスがiであり、文字が0でない場合、(i-1)最初のインデックスで可能な文字列数に従ってiで復号できます.現在の1つの数が1の場合、前の数が2の場合、現在の数が6以下の場合(<=26)(i-2)は、i番目のインデックスで可能な文字列数に基づいて復号することができる.
アルゴリズムは以下の通りです.

文字列が0で始まると、0が返されます.

0および1文字が与えられると、復号可能な数字は1に設定される.

の2番目の文字(ith index)から探索を開始します.
a.前の文字が0でない場合、(i-1)th indexに復号可能な数字を追加する.
b.現在の文字が0で、前の文字が1または2でない場合、0を返します.
c.前の文字が1、または前の文字が2で、現在の文字が6以下である場合、(i-2)th indexに復号可能な数字を追加する.

n番目の文字列に復号可能な数字が返されます.

Solution

class Solution {
    int[] dp;

    public int numDecodings(String s) {
    	dp = new int[s.length()+1];

        if (s.startsWith("0"))
            return 0;
        dp[0] = 1;
        dp[1] = 1;

        for (int i=2; i <= s.length(); i++) {
            if (s.charAt(i-1) != '0')
                dp[i] += dp[i-1];
            else {
                if (s.charAt(i-2) != '1' && s.charAt(i-2) != '2')
                    return 0;
            }
            if (s.charAt(i-2) == '1' || (s.charAt(i-2) == '2' && s.charAt(i-1) <= '6'))
                dp[i] += dp[i-2];
        }

        return dp[s.length()];
    }
}

Reference
https://leetcode.com/problems/decode-ways/