LeetCode --- 91. Decode Ways

タイトルリンク: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.
この問題の要求は、数字だけを含む文字列にいくつかの符号化方式がある可能性があると判断することである.
dp[i]は、文字列の前のi文字の可能な符号化方式の数を表すように動的に計画される.では、プッシュ式は次のようになります.
現在の数字が0であれば、前の数字は必ず1または2である.そうでなければ符号化変換ができない.この場合の数字0は前の1または2と接続して符号化するしかないので、dp[i]=dp[i-2]である.
前の数字が1または前の数字が2で、現在の数字が1~6の間であれば、説明はいずれも2種類の符号化(別々または一緒に)可能であるため、dp[i]=dp[i-1]+dp[i-2];.
その他の場合、現在の数値は単独で符号化変換されなければならないため、dp[i]=dp[i-1]となる.
時間複雑度:O(n)
空間複雑度:O(n)

 1 class Solution
 2 {
 3 public:
 4     int numDecodings(string s)
 5     {
 6         if(s == "" || s[0] == '0')
 7             return 0;
 8             
 9         vector<int> dp(s.size() + 1, 0);
10         dp[0] = 1, dp[1] = 1;
11 
12         for(int i = 2; i <= s.size(); ++ i)
13         {
14             if(s[i - 1] == '0')
15             {
16                 if(s[i - 2] >= '1' && s[i - 2] <= '2')
17                     dp[i] = dp[i - 2];
18                 else
19                     return 0;
20             }
21             else
22             {
23                 if(s[i - 2] == '1' || s[i - 2] == '2' && s[i - 1] >= '1' && s[i - 1] <= '6')
24                     dp[i] = dp[i - 1] + dp[i - 2];
25                 else
26                     dp[i] = dp[i - 1];
27             }
28         }
29         
30         return dp[s.size()];
31     }
32 };

繰返し式では,前の2つの結果のみを利用しているので,dp配列を申請して前の状態を保存する必要はなく,前の2つの状態を2つの変数a 1とa 2で保存するだけで空間的複雑度がO(1)に低下することに留意されたい.
時間複雑度:O(n)
空間複雑度:O(1)

 1 class Solution
 2 {
 3 public:
 4     int numDecodings(string s)
 5     {
 6         if(s == "" || s[0] == '0')
 7             return 0;
 8         
 9         int a1 = 1, a2 = 1, a3 = 1;
10         for(int i = 1; i < s.size(); ++ i)
11         {
12             if(s[i] == '0')
13             {
14                 if(s[i - 1] >= '1' && s[i - 1] <= '2')
15                     a3 = a1;
16                 else
17                     return 0;
18             }
19             else
20             {
21                 if(s[i - 1] == '1' || s[i - 1] == '2' && s[i] >= '1' && s[i] <= '6')
22                     a3 = a1 + a2;
23                 else
24                     a3 = a2;
25             }
26             
27             a1 = a2;
28             a2 = a3;
29         }
30         
31         return a3;
32     }
33 };

転載は出典を説明してください:LeetCode---91.Decode Ways