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.Solution: dynamic programming; pay attention to the erroneous cases, like "....00...", or "...40...".
class Solution { public: int numDecodings(string s) { // Note: The Solution object is instantiated only once and is reused by each test case. int n = s.size(); if(n==0) return 0; vector<int> num(n, 1); //basic case if(s[0]=='0') return 0; for(int i=1; i<n; i++){ if(s[i]=='0' && s[i-1]=='0') return 0; if(s[i-1]=='0') num[i]=num[i-1]; else if(s[i]=='0'){ if(s[i-1]>'2') return 0; num[i]=(i==1?1:num[i-2]); } else if(10*(s[i-1]-'0')+(s[i]-'0')<=26) num[i]=num[i-1]+(i==1?1:num[i-2]); else num[i]=num[i-1]; } return num.back(); } };
No comments:
Post a Comment