Description:
A message containing letters from A-Z can be encoded into numbers using the following mapping:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:
"AAJF"with the grouping(1 1 10 6)"KJF"with the grouping(11 10 6)
Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".
Given a string s containing only digits, return the number of ways to decode it.
The test cases are generated so that the answer fits in a 32-bit integer.
Examples:
Example 1:
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3:
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").Solution in Python:
To solve the problem of counting the number of ways to decode a given string s containing only digits, we can use dynamic programming (DP). The idea is to use a DP array where each element dp[i] represents the number of ways to decode the substring s[:i].
Step-by-step explanation of the solution:
Initialization:
- We use a DP array
dpof lengthn + 1, wherenis the length of the input strings. dp[0]is initialized to 1 because there is one way to decode an empty string.dp[1]depends on whether the first character is a valid single-digit decode.
Filling the DP Array:
- For each character in the string starting from the second character, check if the current character can be a valid single-digit decode (
1-9). - Also, check if the current character and the previous character together can be a valid two-digit decode (
10-26). - Update
dp[i]based on these checks.
Return the Result:
- The value at
dp[n]will give the number of ways to decode the entire strings.
Python
class Solution:
def numDecodings(self, s: str) -> int:
if not s or s[0] == '0':
return 0
n = len(s)
dp = [0] * (n + 1)
# Base cases
dp[0] = 1 # There's one way to decode an empty string.
dp[1] = 1 # There's one way to decode a string if the first character is valid.
for i in range(2, n + 1):
# Check if the current character is a valid single-digit decode (1-9).
if s[i-1] != '0':
dp[i] += dp[i-1]
# Check if the last two characters form a valid two-digit decode (10-26).
two_digit = int(s[i-2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i-2]
return dp[n]Explanation of the Code:
- Base Case Initialization:
dp[0] = 1: There is one way to decode an empty string.dp[1] = 1: There is one way to decode the first character if it’s valid (i.e., not ‘0’).
- Filling the DP Array:
- Single Digit Check:
if s[i-1] != '0': If the current characters[i-1]is not ‘0’, it can be a valid single-digit decode.- We then add
dp[i-1]todp[i]because the number of ways to decode up toiincludes the ways to decode up toi-1plus this single character.
- We then add
- Two-Digit Check:
two_digit = int(s[i-2:i])andif 10 <= two_digit <= 26:- If the substring
s[i-2:i]forms a valid two-digit number between 10 and 26, it can be decoded as a single character. - We then add
dp[i-2]todp[i]because the number of ways to decode up toiincludes the ways to decode up toi-2plus this two-digit character.
- If the substring
- Single Digit Check:
- Return Result: The final value
dp[n]gives the number of ways to decode the entire strings.
This approach ensures that all valid decodings are counted and handles edge cases like leading zeros appropriately.
Solution in Javascript:
JavaScript
/**
* @param {string} s
* @return {number}
*/
var numDecodings = function(s) {
// If the input string is empty or starts with '0', return 0
if (s.length === 0 || s[0] === '0') {
return 0;
}
// Initialize the DP array with zeros
let n = s.length;
let dp = new Array(n + 1).fill(0);
// Base cases
dp[0] = 1; // There is one way to decode an empty string
dp[1] = 1; // There is one way to decode the first character if it is valid
// Fill the DP array
for (let i = 2; i <= n; i++) {
// Check if the current character is a valid single-digit decode (1-9)
if (s[i - 1] !== '0') {
dp[i] += dp[i - 1];
}
// Check if the last two characters form a valid two-digit decode (10-26)
let twoDigit = parseInt(s.substring(i - 2, i));
if (twoDigit >= 10 && twoDigit <= 26) {
dp[i] += dp[i - 2];
}
}
// Return the number of ways to decode the entire string
return dp[n];
};Solution in Java:
Java
class Solution {
public int numDecodings(String s) {
// If the input string is empty or starts with '0', return 0
if (s == null || s.length() == 0 || s.charAt(0) == '0') {
return 0;
}
int n = s.length();
// Initialize the DP array with zeros
int[] dp = new int[n + 1];
// Base cases
dp[0] = 1; // There is one way to decode an empty string
dp[1] = 1; // There is one way to decode the first character if it is valid
// Fill the DP array
for (int i = 2; i <= n; i++) {
// Check if the current character is a valid single-digit decode (1-9)
if (s.charAt(i - 1) != '0') {
dp[i] += dp[i - 1];
}
// Check if the last two characters form a valid two-digit decode (10-26)
int twoDigit = Integer.parseInt(s.substring(i - 2, i));
if (twoDigit >= 10 && twoDigit <= 26) {
dp[i] += dp[i - 2];
}
}
// Return the number of ways to decode the entire string
return dp[n];
}
}Solution in C#:
C#
public class Solution {
public int NumDecodings(string s) {
// Edge case: If the string is empty, there are no ways to decode it
if (string.IsNullOrEmpty(s)) {
return 0;
}
int n = s.Length;
// dp[i] will store the number of ways to decode the substring s[0..i-1]
int[] dp = new int[n + 1];
// There is one way to decode an empty string
dp[0] = 1;
// dp[1] is 1 if the first character is not '0', otherwise it's 0
dp[1] = s[0] != '0' ? 1 : 0;
// Loop through the string starting from the second character
for (int i = 2; i <= n; i++) {
// Check the last one digit and see if it forms a valid number
int oneDigit = int.Parse(s.Substring(i - 1, 1));
if (oneDigit >= 1 && oneDigit <= 9) {
dp[i] += dp[i - 1];
}
// Check the last two digits and see if they form a valid number
int twoDigits = int.Parse(s.Substring(i - 2, 2));
if (twoDigits >= 10 && twoDigits <= 26) {
dp[i] += dp[i - 2];
}
}
// The answer is the number of ways to decode the entire string
return dp[n];
}
}