Leetcode 91. Decode Ways

Problem:

This problem involves number to letter mapping and decoding. The problem gives a mapping of digits from 1 to 26 to the letters from A to Z. Given a non-empty string containing only digits, the task is to determine the total number of ways to decode it.

For instance, if the input string is "12", it can be decoded as "AB" (1 2) or "L" (12), hence the output would be 2. As another example, if the input string is "226", it can be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6), hence the output would be 3.

Solution Approach:

We can solve this problem using Dynamic Programming(DP). The DP approach involves breaking down the problem into smaller sub-problems, solving each sub-problem, and storing the results in an array (DP array). The solution to the main problem is then computed using the stored results.

We maintain a DP array of size n + 1, where n is the length of the input string. In the end, dp[0] will contain the number of ways to decode the entire string. Initially, dp[n] is set as 1, and dp[n - 1] is set as 1 if the last character of the string is not "0", else it is set as 0.

In each iteration, starting from n - 2 till 0, we check if the current character and the group of current and next character can be validly decoded or not.

A single character can be validly decoded if it is not "0". Hence, if the current character at i position is validly decoded, we add dp[i + 1] to dp[i], because dp[i + 1] already contains the number of ways to decode the string from i + 1 to n.

Similarly, a group of two characters can be validly decoded if the first character is "1" (as it can be mapped to any character from "A" to "Z") or the first character is “2” and the second character is less than "7" (as it can be mapped to any character from "A" to "Z"). Hence, if the current character at i and i + 1 positions can be validly decoded, we add dp[i + 2] to dp[i], because dp[i + 2] already contains the number of ways to decode the string from i + 2 to n.

In the end, dp[0] will contain the number of ways to decode the entire string.

Python Solution

1
2python
3class Solution:
4    def numDecodings(self, s):
5        n = len(s)
6        dp = [0] * (n + 1)
7        dp[n] = 1
8        dp[n - 1] = 1 if s[n - 1] != "0" else 0
9
10        for i in range(n - 2, -1, -1):
11            if s[i] != "0":
12                dp[i] += dp[i + 1]
13            if s[i] == "1" or (s[i] == "2" and s[i + 1] < "7"):
14                dp[i] += dp[i + 2]
15        
16        return dp[0]

Java Solution

1
2java
3class Solution {
4    public int numDecodings(String s) {
5        int n = s.length();
6        int[] dp = new int[n + 1];
7        dp[n] = 1;
8        dp[n - 1] = s.charAt(n - 1) != '0' ? 1 : 0;
9
10        for (int i = n - 2; i >= 0; i--) {
11            if (s.charAt(i) != '0') {
12                dp[i] += dp[i + 1];
13            }
14            if (s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i + 1) < '7')) {
15                dp[i] += dp[i + 2];
16            }
17        }
18        
19        return dp[0];
20    }
21}

JavaScript Solution

1
2javascript
3class Solution {
4    numDecodings(s) {
5        var n = s.length;
6        var dp = new Array(n + 1).fill(0);
7        dp[n] = 1;
8        dp[n - 1] = s[n - 1] != "0" ? 1 : 0;
9
10        for (var i = n - 2; i >= 0; i--) {
11            if (s[i] != "0") {
12                dp[i] += dp[i + 1];
13            }
14            if (s[i] == "1" || (s[i] == "2" && s[i + 1] < "7")) {
15                dp[i] += dp[i + 2];
16            }
17        }
18        
19        return dp[0];
20    }
21}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int numDecodings(string s) {
6        int n = s.length();
7        vector<int> dp(n + 1, 0);
8        dp[n] = 1;
9        dp[n - 1] = s[n - 1] != '0' ? 1 : 0;
10
11        for (int i = n - 2; i >= 0; --i) {
12            if (s[i] != '0') {
13                dp[i] += dp[i + 1];
14            }
15            if (s[i] == '1' || (s[i] == '2' && s[i + 1] < '7')) {
16                dp[i] += dp[i + 2];
17            }
18        }
19        
20        return dp[0];
21    }
22};

C# Solution

1
2csharp
3public class Solution {
4    public int NumDecodings(string s) {
5        int n = s.Length;
6        int[] dp = new int[n + 1];
7        dp[n] = 1;
8        dp[n - 1] = s[n - 1] != '0' ? 1 : 0;
9
10        for (int i = n - 2; i >= 0; --i) {
11            if (s[i] != '0') {
12                dp[i] += dp[i + 1];
13            }
14            if (s[i] == '1' || (s[i] == '2' && s[i + 1] < '7')) {
15                dp[i] += dp[i + 2];
16            }
17        }
18        
19        return dp[0];
20    }
21}

This problem is basically about finding the number of valid interpretations of a string comprised of numbers. To find the solution, we used dynamic programming and maintained an array that kept track of the number of ways to decode each substring. A one-digit number can be decoded if it's not zero, and a two-digit number can be decoded if it's either 10-19 or 20-26. The solutions provided cover various popular programming languages such as Python, Java, JavaScript, C++, and C#.

It is also interesting to note that this problem is an example of overlapping subproblems since the same subproblems are being solved multiple times (i.e., the cumulative number of ways to decode each substring). The utilization of a DP array to keep track of already computed results is a major optimization over naive solution approaches and quite a common strategy in dynamic programming.

Moreover, the complexity of this solution is O(n), where n is the length of the string. This is because we are iterating over the string once and filling up the dp array in a bottom-up manner. The space complexity is also O(n), because of the extra space used by the dp array.

This dynamic programming approach to solving this problem is efficient and practical. In terms of real-world applications, this kind of problem might appear in cryptography or coding theory where you might need to decode an encoded message. In general, the techniques used to solve this problem could be used in any scenario where we need to find all possible combinations or arrangements of a set of elements based on a specific rule or restriction.