Tuesday, April 22, 2014

Leetcode (Python): Decode Ways

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).
The number of ways decoding "12" is 2.

Solution:

Notice that the number of ways of decoding a string till the ith character is the number of ways of deciding till the previous one (if the ith character is not '0') plus the number of ways to decode till two before (if the last two characters make a valid letter coding, i.e. from 10 till 26).

class Solution:
    # @param s, a string
    # @return an integer
    def numDecodings(self, s):
        if len(s) == 0:
            return 0
        previous = 0
        actual = 1
        for i in range(0,len(s)):
            if not s[i].isdigit():
                return 0
            temp = 0
            if s[i]!='0':
                temp = actual
            if i>0 and s[i-1]!= '0' and int(s[i-1:i+1])<27:
                temp += previous
            previous = actual
            actual = temp
        return actual

No comments :

Post a Comment