Decode Ways

Description

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.

Example
Given encoded message 12, it could be decoded as AB (1 2) or L (12).
The number of ways decoding 12 is 2.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param s a string,  encoded message
     * @return an integer, the number of ways decoding
     */
    int numDecodings(string& s) {
        // Write your code here
        if (s.empty() || s[0] == '0') {
            return 0;
        }
        int len = s.size();
        int prev = 1;
        int cur  = 1;
        for (int i = 1; i < len; ++i) {
            // for s[i] = 0, we have only one decode way and need to disconnect
            // current counter
            if (s[i] == '0') {
                cur = 0;
            }
            // for two decode ways s[i-1] s[i] < 26 or s[i-1] < 2
            if ((s[i-1]  == '2' && s[i] <= '6') || s[i-1] == '1') {
                cur = cur + prev;
                prev = cur - prev;
            } else {
                prev = cur;
            }
        }
        return cur;
    }
};

Similar problems

x

Tags

x