Alibi

My Life is Getting Better

Leetcode[91] Decode Ways

06 Nov 2015

###Task 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.

###Python

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s == None or len(s) == 0:
            return 0
        dp = [0 for i in range(len(s) + 1)]
        #dp[i] stands for the number of ways to decode str[:i]
        dp[0] = 1
        if self.isChar(s[0]):
            dp[1] = 1
        else:
            dp[1] = 0
        for i in range(2, len(s) + 1):
            if self.isChar(s[i - 1: i]):
                dp[i] += dp[i - 1]
            if self.isChar(s[i - 2: i]):
                dp[i] += dp[i - 2]
        return dp[len(s)]
        
    def isChar(self, s):
        if s[0] == '0':
            return False
        return int(s) > 0 and int(s) < 27

###Java

public class Solution {
	public boolean isValid(String s) {
		if (s.charAt(0) == '0') {
			return false;
		}
		int num = Integer.parseInt(s);
		return num >= 1 && num <= 26;
	}

    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') {
        	return 0;
        }

        int[] dp = new int[s.length() + 1]; //dp[i] stands for how many solutions the prev-i has

        dp[0] = 1;
        if (isValid(s.substring(0, 1))) {
        	dp[1] = 1;
        } else {
        	dp[1] = 0;
        }

        for (int i = 2; i <= s.length(); i++) {
        	if (isValid(s.substring(i - 1, i))) {
        		dp[i] += dp[i - 1];
        	}
        	if (isValid(s.substring(i - 2, i))) {
        		dp[i] += dp[i - 2];
        	}
        }

        return dp[s.length()];
    }
}

###Points

Related Posts