A message containing letters from
A-Z
is being encoded to numbers using the following mapping:
'A' -> 1 'B' -> 2 ... 'Z' -> 26Given 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.
A:
-------------------------------DP ----------------------------
class Solution { public: int numDecodings(string s) { int n = s.length(); vector<int> count(n+1, 0); count[0] = 1; // so as to avoid checking boundary for(int i =0;i < n;++i) { if(s[i]>='1' && s[i]<='9') count[i+1] = count[i]; if(i>0) { string s2 = s.substr(i-1,2); // substr(startIndex, length) int val = stoi(s2); if(val>=10 && val <=26 ) { count[i+1] += count[i-1]; } } } return count[n]; } };
Mistakes:
1: 哎,一开始,竟然看成是输入为ABC类了。Tiger,你得多SB啊~~~
光为了简洁代码了,输入都没有检测,哎~~~~~~~
2: 当i-2<0的时候, 应该还是 += 而不是简单的 =1
教训啊, 不要为了狗屁不如的代码简洁。 那个不重要, 首先要保证正确。
3: valid (2个char )的时候, 首先要看,第一个是否是0, 如果是, 就不对。
-------------------------3 rd Pass---------------------思路同上------------------------
代码打了很多补丁,就不写到这里了。
Error:
1:开始没有考虑检查输入是否valid的情况, 例如输入为”0“
2:第一稿的时候,直很一厢情愿地,认为不会有"10"的输入, 或者说,不会有0这个数字。 艹,太SB 了。
No comments:
Post a Comment