Sunday, April 28, 2013

Leetcode: Decode Ways in C++



A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Solution: 

int numDecodings(string s) {
         if(s.size() == 0)
            return 0;
        vector<int> ways(s.size() + 1,0);
        ways[s.size()] =1;
        for(int i = s.size() - 1; i >= 0; --i)
        {
            //one digit number
            if(s[i] == '0')
                ways[i] = 0;
            else
                ways[i] = ways[i+1];
            
            //two digit number
            if( i + 1 < s.size() && ((s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6')))) {
                ways[i] += ways[i + 2];
            }
        }
        return ways[0];
    }

No comments:

Post a Comment