Dynamic Programming
Decode Ways
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
You are given a string s containing only digits. Write a function to return the number of ways to decode using the following mapping:
'1' -> "A" '2' -> "B" '3' -> "C" ... '26' -> "Z"
There may be multiple ways to decode a string. For example, "14" can be decoded as "AD" or "N".
Input:
s = 101
Output:
1
Explanation: The only way to decode it is "JA". "01" cannot be decoded into "A" as "1" and "01" are different.
Explanation
This solution uses a bottom-up dynamic programming approach to solve the problem. We'll walkthrough how the solution solves the problem when the input string is s = 11106.
We create an integer array dp of length n + 1 where n is the length of the input string s. dp[i] is equal to the number of ways to decode the first i characters of the string s. If the first character of the string is 0, we can return 0 immediately. Otherwise, we initialize dp[0] = 1 (there is one way to decode an empty string) and dp[1] = 1 (one way to decode the first character of s).
Visualization
def num_decodings(s):if not s or s[0] == '0':return 0n = len(s)dp = [0] * (n + 1)dp[0], dp[1] = 1, 1for i in range(2, n + 1):digit = int(s[i - 1])if digit != 0:dp[i] += dp[i - 1]digit = int(s[i - 2:i])if 10 <= digit <= 26:dp[i] += dp[i - 2]return dp[n]
decode ways
0 / 1
We then use a for-loop i which goes from 2 to n to iterate through the string. The body of each loop determines the correct value of dp[i] by looking at the previous two characters of the string.
Single Digit
We first check the ith digit of the string. If it is not equal to 0, then the number of ways we to decode the first i characters of the string is equal to the number of ways to decode the first i - 1 characters of the string (each of those ways and the encoding of the ith digit). This allows us to set dp[i] += dp[i - 1].
Visualization
def num_decodings(s):if not s or s[0] == '0':return 0n = len(s)dp = [0] * (n + 1)dp[0], dp[1] = 1, 1for i in range(2, n + 1):digit = int(s[i - 1])if digit != 0:dp[i] += dp[i - 1]digit = int(s[i - 2:i])if 10 <= digit <= 26:dp[i] += dp[i - 2]return dp[n]
i = 2
0 / 2
When it is equal to 0, it's not possible to decode the ith digit alone, so we leave dp[i] as 0 and continue.
Visualization
def num_decodings(s):if not s or s[0] == '0':return 0n = len(s)dp = [0] * (n + 1)dp[0], dp[1] = 1, 1for i in range(2, n + 1):digit = int(s[i - 1])if digit != 0:dp[i] += dp[i - 1]digit = int(s[i - 2:i])if 10 <= digit <= 26:dp[i] += dp[i - 2]return dp[n]
digit = 0
0 / 1
Double Digit
Next, we move onto checking the ith and ith - 1 digits together. If they form a number between 10 and 26 (inclusive), then we can decode the ith and ith - 1 digits together. This means we have an additional dp[i - 2] ways to decode the first i characters of the string (each of those ways and the encoding of the ith and ith - 1 digits). This allows us to set dp[i] += dp[i - 2].
Visualization
def num_decodings(s):if not s or s[0] == '0':return 0n = len(s)dp = [0] * (n + 1)dp[0], dp[1] = 1, 1for i in range(2, n + 1):digit = int(s[i - 1])if digit != 0:dp[i] += dp[i - 1]digit = int(s[i - 2:i])if 10 <= digit <= 26:dp[i] += dp[i - 2]return dp[n]
digit = 11
0 / 2
Finally, we return dp[n] which is the number of ways to decode the entire string.
Solution
Visualization
Try these examples:
def num_decodings(s):if not s or s[0] == '0':return 0n = len(s)dp = [0] * (n + 1)dp[0], dp[1] = 1, 1for i in range(2, n + 1):digit = int(s[i - 1])if digit != 0:dp[i] += dp[i - 1]digit = int(s[i - 2:i])if 10 <= digit <= 26:dp[i] += dp[i - 2]return dp[n]
decode ways
0 / 20
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) where n is the length of the string. We iterate through the string once.
Space Complexity: O(n) where n is the length of the string. We use an array of length n + 1 to store the number of ways to decode the first i characters of the string.
Mark as read
Your account is free and you can post anonymously if you choose.