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()]; } }; ```

1 comment:

1. dp[0]如果按你的定义指的是长度为0的解码方法数，第一感觉应该初始成0.
能不能说一下怎么想出来要初始成1呢，是到dp[2]的时候试出来的么.
dp初始化一般怎么想?