## Tuesday, November 25, 2014

### [LeetCode] 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.

1. 如果XY<=26，那么能解码成h[X], h[Y], h[XY]
2. 否则，只能解码成h[X], h[Y]

1. dp[0] = 1，dp[1] = 0
2. v = s[i-1]*10+s[i]：
v<=26： dp[i+1] = dp[i] + dp[i-1]
v>26：dp[i+1] = dp[i]

corner case：有0的情况
Y = 0：显然无法解码成h[Y]，此时只能看h[XY]是否valid：dp[i+1] = dp[i-1]
X = 0：显然无法解码成h[XY]，此时dp[i+1] = dp[i]

XY可以解码的条件是：9<XY<=26
Y可以单独解码的条件是：Y != '0'

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17``` ```class Solution { public: int numDecodings(string s) { if(s.empty() || s[0]<'1' || s[0]>'9') return 0; vector dp(s.size()+1,0); dp[0] = dp[1] = 1; for(int i=1; i9) dp[i+1] += dp[i-1]; if(s[i]!='0') dp[i+1] += dp[i]; if(dp[i+1]==0) return 0; } return dp[s.size()]; } }; ```