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: 2Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"Output: 3Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
解法1: 递归， Time: O(2^n)
解法2：动态规划Dynamic Programming。一位数时不能为0，两位数不能大于26，其十位上的数也不能为0。用哈希表来存或者用两个变量来存。
State: dp[i]，代表i之前的数字的解法数量。注意index：dp长度比数组多1，所以 s[i-1]是当前数字，dp[i]是当前数字的解法数。
Function: dp[i] = dp[i - 1] (if s[i - 1] != 0) + dp[i - 2] (if s[i - 2] == 1 or s[i - 2] == 2 and i -1 < = 6)
Initialize: dp[0] = 0, dp[1] = 1
Return: dp[n]
Java: Recursive
int numDecodings(string s) { return s.empty() ? 0: numDecodings(0,s); } int numDecodings(int p, string& s) { int n = s.size(); if(p == n) return 1; if(s[p] == '0') return 0; int res = numDecodings(p+1,s); if( p < n-1 && (s[p]=='1'|| (s[p]=='2'&& s[p+1]<'7'))) res += numDecodings(p+2,s); return res; } Java: Memoization O(n)
int numDecodings(string s) { int n = s.size(); vector mem(n+1,-1); mem[n]=1; return s.empty()? 0 : num(0,s,mem); } int num(int i, string &s, vector &mem) { if(mem[i]>-1) return mem[i]; if(s[i]=='0') return mem[i] = 0; int res = num(i+1,s,mem); if(i Java: dp, O(n) time and space
int numDecodings(string s) { int n = s.size(); vector dp(n+1); dp[n] = 1; for(int i=n-1;i>=0;i--) { if(s[i]=='0') dp[i]=0; else { dp[i] = dp[i+1]; if(i Java: dp, constance space
int numDecodings(string s) { int p = 1, pp, n = s.size(); for(int i=n-1;i>=0;i--) { int cur = s[i]=='0' ? 0 : p; if(i Java:
public class Solution { public int numDecodings(String s) { if (s.isEmpty() || (s.length() > 1 && s.charAt(0) == '0')) return 0; int[] dp = new int[s.length() + 1]; dp[0] = 1; for (int i = 1; i < dp.length; ++i) { dp[i] = (s.charAt(i - 1) == '0') ? 0 : dp[i - 1]; if (i > 1 && (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))) { dp[i] += dp[i - 2]; } } return dp[s.length()]; }} Java:
public class Solution { public int numDecodings(String s) { if (s.isEmpty() || (s.length() > 1 && s.charAt(0) == '0')) return 0; int prev = 1, prev_prev = 0; for (int i = 0; i < s.length(); i++) { int cur = 0; if (s.charAt(i) != '0') { cur = prev; } if (i > 0 && (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i - 1) <= '6'))) { cur += prev_prev; } prev_prev = prev; prev = cur; } return prev; }} Python: wo
class Solution(object): def numDecodings(self, s): """ :type s: str :rtype: int """ if len(s) == 0 or s[0] == '0': return 0 dp = [0] * (len(s) + 1) dp[0] = 1 for i in xrange(1, len(s) + 1): if s[i-1] != '0': dp[i] = dp[i-1] if i > 1 and (s[i-2] == '1' or (s[i-2] == '2' and int(s[i-1]) <= 6)): dp[i] += dp[i-2] return dp[-1]
Python:
class Solution(object): def numDecodings(self, s): if len(s) == 0 or s[0] == '0': return 0 prev, prev_prev = 1, 0 for i in xrange(len(s)): cur = 0 if s[i] != '0': cur = prev if i > 0 and (s[i - 1] == '1' or (s[i - 1] == '2' and s[i] <= '6')): cur += prev_prev prev, prev_prev = cur, prev return prev
C++:
class Solution {public: int numDecodings(string s) { if (s.empty() || (s.size() > 1 && s[0] == '0')) return 0; vector dp(s.size() + 1, 0); dp[0] = 1; for (int i = 1; i < dp.size(); ++i) { dp[i] = (s[i - 1] == '0') ? 0 : dp[i - 1]; if (i > 1 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) { dp[i] += dp[i - 2]; } } return dp.back(); }}; C++:
class Solution {public: int numDecodings(string s) { if (s.empty()) return 0; vector dp(s.size() + 1, 0); dp[0] = 1; for (int i = 1; i < dp.size(); ++i) { if (s[i - 1] != '0') dp[i] += dp[i - 1]; if (i >= 2 && s.substr(i - 2, 2) <= "26" && s.substr(i - 2, 2) >= "10") { dp[i] += dp[i - 2]; } } return dp.back(); }}; C++:
class Solution {public: int numDecodings(string s) { if (s.empty() || s.front() == '0') return 0; int c1 = 1, c2 = 1; for (int i = 1; i < s.size(); ++i) { if (s[i] == '0') c1 = 0; if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) { c1 = c1 + c2; c2 = c1 - c2; } else { c2 = c1; } } return c1; }};
类似题目：