NUHMAN.com

Introduction

LeetCode 91: Decode Ways is a dynamic programming problem that asks you to determine how many ways you can decode a given string of digits, where each digit corresponds to a letter from 'A' to 'Z'. For example, '1' corresponds to 'A', '2' corresponds to 'B', and so on, up to '26' which corresponds to 'Z'.

The problem involves finding all possible decodings of the string, which can be done using dynamic programming to break down the problem into manageable subproblems.

Problem Statement

Given a string s consisting of digits, return the total number of ways to decode it. The decoding rules are:

• '1' -> 'A'
• '2' -> 'B'
• ...
• '26' -> 'Z'

You may assume that the input string will not have leading zeros, unless the string is "0", in which case no decoding is possible.

Example:

go

Input: s = "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Approach: Dynamic Programming

Strategy:

The key to solving this problem efficiently is dynamic programming (DP). We can break the string down into subproblems, where each subproblem represents how many ways we can decode the substring up to a certain position.

The idea is to use a DP array (dp) where:

• dp[i] represents the number of ways to decode the substring s[0:i].

Steps:

1. Base Cases:

• dp[0] = 1: There's one way to decode an empty string.
• dp[1]: If s[0] is not '0', then there's one way to decode the string of length 1 (i.e., dp[1] = 1).

1. Recurrence Relation:

• If the current digit s[i-1] is between '1' and '9', then dp[i] can include all the ways to decode the substring s[0:i-1].
• If the last two digits form a number between '10' and '26', we can also decode it as a two-character letter, so we add the number of ways to decode the substring s[0:i-2].

1. Final Answer:

• The value of dp[n] (where n is the length of the string) will give the total number of ways to decode the string.

Go Implementation

go

func numDecodings(s string) int {
    if len(s) == 0 || s[0] == '0' {
        return 0
    }
    
    n := len(s)
    dp := make([]int, n+1)
    dp[0] = 1
    dp[1] = 1

    for i := 2; i <= n; i++ {
        // Check single digit
        if s[i-1] != '0' {
            dp[i] += dp[i-1]
        }
        
        // Check two digits
        if s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6') {
            dp[i] += dp[i-2]
        }
    }

    return dp[n]
}

Explanation

1. Initialization:

• We initialize a dp array with n+1 elements (where n is the length of the string). dp[0] is set to 1 because there is one way to decode an empty string.
• dp[1] is initialized to 1, assuming the first character is not '0'. If s[0] is '0', there are no valid decodings, and the function will return 0.

1. Filling the DP Array:

• For each index i from 2 to n, we consider two possibilities:
• Single-digit decode: If the current character s[i-1] is between '1' and '9', then we can add dp[i-1] to dp[i].
• Two-digit decode: If the last two characters form a valid number between '10' and '26' (i.e., "10" to "26"), we can add dp[i-2] to dp[i].

1. Result:

• The result is stored in dp[n], which gives the number of ways to decode the entire string.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n)

Where n is the length of the input string.

• The time complexity is O(n) because we iterate over the string once.
• The space complexity is O(n) because we use an array dp of size n+1 to store the number of ways to decode substrings.

Edge Cases

1. Empty string: An empty string cannot be decoded, so the result should be 0.

• Example: s = ""
• Output: 0

1. String starting with '0': A string starting with '0' cannot be decoded because there’s no valid encoding for '0'.

• Example: s = "01"
• Output: 0

1. String with a valid '0': If the string contains a '0' but it's part of a valid two-digit number like '10' or '20', it can still be decoded.

• Example: s = "10"
• Output: 1 (decoded as "J")

1. Long string: The solution efficiently handles long strings by using dynamic programming, ensuring the solution runs in linear time.

Conclusion

LeetCode 91: Decode Ways is a problem that requires careful handling of edge cases, particularly when dealing with numbers that can be decoded as both single and two-digit values. Using dynamic programming allows us to break the problem down into smaller subproblems and build up the solution efficiently.

The O(n) time complexity ensures that even larger strings are handled efficiently, while the O(n) space complexity ensures we only use as much space as necessary to store intermediate results.

This problem is an excellent exercise in dynamic programming and string manipulation, particularly when handling combinatorial problems involving valid ranges of numbers.