LeetCode #91: Decode Ways

LeetCode Solutions

https://leetcode.com/problems/decode-ways/

We can solve this problem by using dynamic programming. Let’s start by considering each character of the string s one by one, and find the number of ways it can be decoded. We will use two pointers to keep track of the current character and the previous character.

Now, let’s consider two cases:

  1. If the current character is not ‘0’, then it can be decoded alone, and we can count the number of ways to decode the previous character (two_back) in addition to the number of ways to decode the current character (one_back).
  2. If the current character and the previous character can be decoded together, then we can count the number of ways to decode the character two steps back (two_back) in addition to the number of ways to decode the current and the previous character together (one_back).

We can keep track of the count using two variables: one_back and two_back, and update them for each character in the string.

Steps to Solve the Problem

  1. If the first character is ‘0’, return 0 as it cannot be decoded.
  2. Initialize two variables: one_back and two_back to 1, which represents the number of ways to decode one and two characters, respectively.
  3. Loop through each character in the string s from the second character.
  4. If the current character can be decoded alone (i.e., it is not ‘0’), add the number of ways to decode the previous character (two_back) to the number of ways to decode the current character (one_back).
  5. If the current and the previous characters can be decoded together, add the number of ways to decode two steps back (two_back) to the number of ways to decode the current and the previous character (one_back).
  6. Update the two_back and one_back variables.
  7. Return the final value of one_back, which represents the total number of ways to decode the input string s.

Solution

Here’s the Python code for the solution:

class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == "0":
            return 0
        two_back = 1
        one_back = 1
        for i in range(1, len(s)):
            current = 0
            if s[i] != "0":
                current = one_back
            two_digit = int(s[i - 1: i + 1])
            if two_digit >= 10 and two_digit <= 26:
                current += two_back
            two_back = one_back
            one_back = current
        
        return one_back

Time and Space Complexity

The time complexity of this solution is O(n), where n is the length of the input string s. This is because we are looping through each character in the string once.

The space complexity of this solution is O(1), because we are only using two variables to keep track of the number of ways to decode the characters. Therefore, the space required does not depend on the length of the input