題目:
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).
leetcode15。The number of ways decoding?"12"
?is 2. (Medium)
?
分析:
開始想到的就是暴力搜索,但是超時了,所以考慮用動態規劃來做。
符合單序列動態規劃的特點,所以有
leetcode 1、1. 狀態:dp[i]表示前i個字符組成的子串可能的解碼方式。
2. 初始化:dp[0] = 1, dp[1] = 1(s[0] != '0',因為沒有0這個對應數字)
3. 遞推關系:
一般情況下:
if s[i - 1]與s[i -2]組成的在“1” ~“26”范圍內, dp[i] = dp[i - 1] + dp[i - 2];
LeetCode、 else, dp[i] = dp[i - 1];
但要注意的是,如果s[i - 1] == '0'需要特殊處理,當s[i - 2] == '1' || '2'時, dp[i] = dp[i - 2]
否則,則說明這個0沒有對應位,這個字符串無法解碼,直接返回0;
4.結果: dp[s.size()];
代碼:
1 class Solution { 2 public: 3 int numDecodings(string s) { 4 if (s.size() == 0) { 5 return 0; 6 } 7 int dp[s.size() + 1]; 8 dp[0] = 1; 9 if (s[0] != '0') { 10 dp[1] = 1; 11 } 12 for (int i = 2; i <= s.size(); ++i) { 13 if (s[i - 1] == '0') { 14 if (s[i - 2] == '1' || s[i - 2] == '2') { 15 dp[i] = dp[i - 2]; 16 continue; 17 } 18 else { 19 return 0; 20 } 21 } 22 if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6') ) { 23 dp[i] = dp[i - 1] + dp[i - 2]; 24 } 25 else { 26 dp[i] = dp[i - 1]; 27 } 28 } 29 return dp[s.size()]; 30 } 31 };
LeetCode Online Judge??
?
?
?
2. 遞推關系: