Your 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 botton-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).
defnum_decodings(s):
ifnot s or s[0]=='0':
return0
n =len(s)
dp =[0]*(n +1)
dp[0], dp[1]=1,1
for i inrange(2, n +1):
digit =int(s[i -1])
if digit !=0:
dp[i]+= dp[i -1]
digit =int(s[i -2:i])
if10<= digit <=26:
dp[i]+= dp[i -2]
return dp[n]
decode ways
0 / 1
Python
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].
defnum_decodings(s):
ifnot s or s[0]=='0':
return0
n =len(s)
dp =[0]*(n +1)
dp[0], dp[1]=1,1
for i inrange(2, n +1):
digit =int(s[i -1])
if digit !=0:
dp[i]+= dp[i -1]
digit =int(s[i -2:i])
if10<= digit <=26:
dp[i]+= dp[i -2]
return dp[n]
i = 2
0 / 2
Python
Handling a single digit.
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.
defnum_decodings(s):
ifnot s or s[0]=='0':
return0
n =len(s)
dp =[0]*(n +1)
dp[0], dp[1]=1,1
for i inrange(2, n +1):
digit =int(s[i -1])
if digit !=0:
dp[i]+= dp[i -1]
digit =int(s[i -2:i])
if10<= digit <=26:
dp[i]+= dp[i -2]
return dp[n]
digit = 0
0 / 1
Python
Handling a single digit.
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].
defnum_decodings(s):
ifnot s or s[0]=='0':
return0
n =len(s)
dp =[0]*(n +1)
dp[0], dp[1]=1,1
for i inrange(2, n +1):
digit =int(s[i -1])
if digit !=0:
dp[i]+= dp[i -1]
digit =int(s[i -2:i])
if10<= digit <=26:
dp[i]+= dp[i -2]
return dp[n]
digit = 11
0 / 2
Python
Handling a double digit.
Finally, we return dp[n] which is the number of ways to decode the entire string.
Solution
defnum_decodings(s):
ifnot s or s[0]=='0':
return0
n =len(s)
dp =[0]*(n +1)
dp[0], dp[1]=1,1
for i inrange(2, n +1):
digit =int(s[i -1])
if digit !=0:
dp[i]+= dp[i -1]
digit =int(s[i -2:i])
if10<= digit <=26:
dp[i]+= dp[i -2]
return dp[n]
decode ways
0 / 20
Python
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.
Your account is free and you can post anonymously if you choose.