menu

[LeetCode] 091. Decode Ways *

Problem (Medium)

091. 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 a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

  • Input: “12”
  • Output: 2
  • Explanation: It could be decoded as “AB” (1 2) or “L” (12).

Example 2:

  • Input: “226”
  • Output: 3
  • Explanation: It could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).

Approach 1: (My Solution) Backtracking (Time Limit Exceeded!)

Idea

Solution

class Solution1:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        res = [0] 
        self.helper(res, s, 0) 
        return res[0]
    def helper(self, res, s, pos):
        if pos == len(s):
            res[0] += 1
            return

        if s[pos] != '0':
            self.helper(res, s, pos+1)
        if int(s[pos:pos+2]) in range(10, 27) and pos+2 <= len(s):
            self.helper(res, s, pos+2)

Complexity

  • Time: $O()$
  • Space: $O()$

Approach 2: DP *

Idea

  • DP state:

  • Initial state:

    • dp[0] = 1;
    • dp[1] = 0 if s[0] == ‘0’ else 1.

Solution

class Solution2:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not len(s):
            return 0
        dp = [0 for _ in range(len(s)+1)]
        dp[0] = 1
        dp[1] = 0 if s[0] == '0' else 1

        for i in range(2, len(dp)):
            if s[i-1] != '0':
                dp[i] = dp[i-1]
            if int(s[i-2:i]) in range(10, 27):
                dp[i] += dp[i-2]
        return dp[-1]

Complexity

  • Time: $O()$
  • Space: $O()$



KF

Comments