Problem Statement:
You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:
"1" -> 'A'
"2" -> 'B'
...
"25" -> 'Y'
"26" -> 'Z'
However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs code”25″).
For example, "11106" can be decoded into:
"AAJF"with the grouping(1, 1, 10, 6)"KJF"with the grouping(11, 10, 6)- The grouping
(1, 11, 06)is invalid because"06"is not a valid code (only"6"is valid).
Note: there may be strings that are impossible to decode.
Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: s = “12”
Output: “12”
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”). In this case, the string is not a valid encoding, so return 0.
Constraints
1 <= s.length <= 100scontains only digits and may contain leading zero(s).
Approach:
- Recursive with Memoization (Top-down DP)
- Define a recursive function
fn(remS) → returns numberof decodings for substringremS. - Base case: if string becomes empty →
1 valid decoding. - Memoization: Store results in
dpto avoid recomputation.
- Define a recursive function
- Choices at each step (from right side):
- One digit: If last digit is not
"0", decode it → recursive call on substring without last digit. - Two digits: If last two digits form a
number between 10–26, decode it → recursive call on substring withoutlast two digits.
- One digit: If last digit is not
- Add both possibilities → total ways for that substring.
Time & Space Complexity:
Time Complexity: O(n)
Space Complexity: O(n)
Dry Run
Input: s = "226"
Step 0: Start Function numDecodings("226")
dp = {}
Call fn("226"):
fn("226"):
- remS = "226" (not empty, not in dp)
- n = 3
- oneDigit = remS.substring(2) = "6"
- twoDigit = remS.substring(1) = "26"
- ans = 0
Check oneDigit != 0:
- "6" != 0 → true (coerces to number 6 != 0)
- ans += fn(remS.substring(0, 2)) → ans += fn("22")
Check twoDigit >= 10 && twoDigit <= 26:
- "26" coerces to 26 → 26 >= 10 && 26 <= 26 → true
- ans += fn(remS.substring(0, 1)) → ans += fn("2")
Evaluate fn("22") (from oneDigit path of "226"):
fn("22"):
- remS = "22"
- n = 2
- oneDigit = remS.substring(1) = "2"
- twoDigit = remS.substring(0) = "22"
- ans = 0
oneDigit != 0:
- "2" != 0 → true
- ans += fn(remS.substring(0,1)) → ans += fn("2")
twoDigit >=10 && twoDigit <=26:
- "22" → 22 between 10 and 26 → true
- ans += fn(remS.substring(0,0)) → ans += fn("")
Evaluate fn("2") (first time, called from fn("22")):
fn("2"):
- remS = "2"
- n = 1
- oneDigit = remS.substring(0) = "2"
- twoDigit = remS.substring(-1) → treated as substring(0) = "2"
- ans = 0
oneDigit != 0:
- "2" != 0 → true
- ans += fn(remS.substring(0, 0)) → ans += fn("")
twoDigit >=10 && twoDigit <=26:
- "2" → 2 >= 10 ? false → skip
Evaluate fn(""):
- remS = "" → base case → return 1
So fn("2") = 1
(dp still {} at this point)
Back to fn("22"):
- from oneDigit path got 1
- from twoDigit path fn("") = 1
- ans = 1 + 1 = 2
- dp["22"] = 2
Return 2
Evaluate fn("2") (second call, from twoDigit path of "226"):
- fn("2") is now needed again; check dp → not stored under "2" (we computed fn("2") earlier but only stored fn("22"))
- Recompute fn("2") (as above) → returns 1
(Optionally an implementation could memoize "2" later, but current code only stores remS values that were computed; "2" wasn't stored previously.)
Back to fn("226"):
- oneDigit path returned fn("22") = 2
- twoDigit path returned fn("2") = 1
- ans = 2 + 1 = 3
- dp["226"] = 3
Return 3
Step 3: End
Return value = 3
Output: 3
function numDecodings(s) {
const dp = {};
const fn = (remS) => {
if (remS === "") return 1;
if (remS in dp) return dp[remS];
const n = remS.length;
let ans = 0;
// One digit
const oneDigit = remS.substring(n - 1);
if (oneDigit !== "0") {
ans += fn(remS.substring(0, n - 1));
}
// Two digits (ONLY if length >= 2)
if (n >= 2) {
const twoDigit = remS.substring(n - 2);
const val = Number(twoDigit);
if (val >= 10 && val <= 26) {
ans += fn(remS.substring(0, n - 2));
}
}
dp[remS] = ans;
return ans;
};
return fn(s);
}
def numDecodings(s):
dp = {}
def fn(remS):
if remS == "":
return 1
if remS in dp:
return dp[remS]
n = len(remS)
oneDigit = remS[n - 1:]
twoDigit = remS[n - 2:] if n >= 2 else ""
ans = 0
if oneDigit != "0":
ans += fn(remS[:n - 1])
if len(twoDigit) == 2 and "10" <= twoDigit <= "26":
ans += fn(remS[:n - 2])
dp[remS] = ans
return ans
return fn(s)
import java.util.HashMap;
class Solution {
public int numDecodings(String s) {
HashMap dp = new HashMap<>();
return fn(s, dp);
}
private int fn(String remS, HashMap dp) {
if (remS.length() == 0) return 1;
if (dp.containsKey(remS)) return dp.get(remS);
int n = remS.length();
String oneDigit = remS.substring(n - 1);
String twoDigit = n >= 2 ? remS.substring(n - 2) : "";
int ans = 0;
if (!oneDigit.equals("0")) {
ans += fn(remS.substring(0, n - 1), dp);
}
if (twoDigit.length() == 2 && twoDigit.compareTo("10") >= 0 && twoDigit.compareTo("26") <= 0) {
ans += fn(remS.substring(0, n - 2), dp);
}
dp.put(remS, ans);
return ans;
}
}
#include <unordered_map>
#include <string>
using namespace std;
class Solution {
public:
unordered_map dp;
int fn(string remS) {
if (remS == "") return 1;
if (dp.count(remS)) return dp[remS];
int n = remS.length();
string oneDigit = remS.substr(n - 1);
string twoDigit = n >= 2 ? remS.substr(n - 2) : "";
int ans = 0;
if (oneDigit != "0") {
ans += fn(remS.substr(0, n - 1));
}
if (twoDigit.length() == 2 && twoDigit >= "10" && twoDigit <= "26") {
ans += fn(remS.substr(0, n - 2));
}
dp[remS] = ans;
return ans;
}
int numDecodings(string s) {
return fn(s);
}
};
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1000
typedef struct {
char key[MAX];
int value;
} Pair;
Pair dp[1000];
int dpSize = 0;
int getDp(char *key) {
for (int i = 0; i < dpSize; i++) {
if (strcmp(dp[i].key, key) == 0)
return dp[i].value;
}
return -1;
}
void setDp(char *key, int value) {
strcpy(dp[dpSize].key, key);
dp[dpSize].value = value;
dpSize++;
}
int fn(char *remS) {
if (strlen(remS) == 0) return 1;
int cached = getDp(remS);
if (cached != -1) return cached;
int n = strlen(remS);
char oneDigit[3], twoDigit[3];
int ans = 0;
strcpy(oneDigit, remS + n - 1);
if (strcmp(oneDigit, "0") != 0) {
char sub[MAX];
strncpy(sub, remS, n - 1);
sub[n - 1] = '\0';
ans += fn(sub);
}
if (n >= 2) {
strcpy(twoDigit, remS + n - 2);
if (strcmp(twoDigit, "10") >= 0 && strcmp(twoDigit, "26") <= 0) {
char sub[MAX];
strncpy(sub, remS, n - 2);
sub[n - 2] = '\0';
ans += fn(sub);
}
}
setDp(remS, ans);
return ans;
}
int numDecodings(char *s) {
return fn(s);
}
using System;
using System.Collections.Generic;
public class Solution {
public int NumDecodings(string s) {
var dp = new Dictionary();
return Fn(s, dp);
}
private int Fn(string remS, Dictionary dp) {
if (remS.Length == 0) return 1;
if (dp.ContainsKey(remS)) return dp[remS];
int n = remS.Length;
string oneDigit = remS.Substring(n - 1);
string twoDigit = n >= 2 ? remS.Substring(n - 2) : "";
int ans = 0;
if (oneDigit != "0") {
ans += Fn(remS.Substring(0, n - 1), dp);
}
if (twoDigit.Length == 2 && String.Compare(twoDigit, "10") >= 0 && String.Compare(twoDigit, "26") <= 0) {
ans += Fn(remS.Substring(0, n - 2), dp);
}
dp[remS] = ans;
return ans;
}
}
