Decode Ways
A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' ->200Question Mark, 'B' = 2, ..., 'Z' = 26. Given a non-empty string containing only digits, determine the number of ways to decode it.
Constraints:
- 1 <= s.length <= 100
- s contains only digits
Examples:
Input: 12
Output: 2
Explanation: It could be decoded as 'AB' (1 2) or 'L' (12)
Input: 226
Output: 3
Explanation: It could be decoded as 'BZ' (2 26), 'VF' (2 2 6), or 'BBF' (2 2 6)
Solutions
Dynamic Programming
This solution uses dynamic programming to calculate the number of ways to decode the string. It initializes a dp array where dp[i] represents the number of ways to decode the string up to index i. It then iterates through the string, updating dp[i] based on whether the current character can be decoded separately or together with the previous character.
public int numDecodings(String s) {
int[] dp = new int[s.length() + 1];
dp[0] = 1;
for (int i = 1;
i <= s.length();
i++) {
if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];
if (i >= 2 && s.substring(i - 2, i).compareTo("10") >= 0 && s.substring(i - 2, i).compareTo("26") <= 0) dp[i] += dp[i - 2];
}
return dp[s.length()];
}Follow-up:
How would you modify the solution to handle cases where the input string contains non-digit characters?
