-
Notifications
You must be signed in to change notification settings - Fork 0
135 — Decode Ways
LeetCode 91 · Medium. A message containing letters A-Z is encoded to numbers using the mapping 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26". 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.
Stand at the front of the digit string and ask: how many ways are there to decode everything from here to the end? The very first decision is local and small — the leading digit either stands alone as a one-letter code (as long as it isn't '0'), or it teams up with the digit right after it to form a two-letter code (as long as that pair is between 10 and 26). Either choice, if valid, hands off to "how many ways to decode the rest," which is the exact same question on a shorter suffix. That self-similar structure — today's count depends only on the count one position ahead and, sometimes, two positions ahead — is 1-D DP wearing a string-parsing disguise.
"Number of ways to decode a digit string" with a "one digit or two digits per letter" rule is the cue: a counting problem where each position's answer is built by combining a fixed, small number of later (or earlier, depending on direction) positions' answers — exactly the 1-D DP shape, just walked over string positions instead of array indices, with an extra validity check (no leading '0', two-digit value in 10...26) gating each branch.
Recurse from every position in the string, trying "take one digit" and, when valid, "take two digits," with no memoization — overlapping suffixes get fully re-solved from multiple earlier positions.
func numDecodingsBruteForce(_ s: String) -> Int {
let chars = Array(s)
let n = chars.count
func waysFrom(_ i: Int) -> Int {
if i == n { return 1 } // reached the end cleanly — one valid decoding
if chars[i] == "0" { return 0 } // a leading zero can never start a valid code
var ways = waysFrom(i + 1) // take one digit
if i + 1 < n {
let twoDigit = (chars[i].wholeNumberValue ?? 0) * 10 + (chars[i + 1].wholeNumberValue ?? 0)
if twoDigit >= 10 && twoDigit <= 26 {
ways += waysFrom(i + 2) // take two digits
}
}
return ways
}
return waysFrom(0)
}
// smoke test
print(numDecodingsBruteForce("12")) // 2 ("AB", "L")
print(numDecodingsBruteForce("226")) // 3 ("BZ", "VF", "BBF")
print(numDecodingsBruteForce("06")) // 0 (leading zero is never valid)Big-O: O(2^n) time — every position branches into "one digit" and (when valid) "two digits," and the same later suffixes get re-explored from multiple branches. O(n) space for the recursion stack.
Tabulate forward, keeping only the number of ways to decode the two shortest prefixes seen so far, and combine them according to whether the current one-digit and two-digit slices are valid.
func numDecodings(_ s: String) -> Int {
let chars = Array(s)
let n = chars.count
guard n > 0, chars[0] != "0" else { return 0 }
guard n > 1 else { return 1 }
var prev2 = 1 // dp[i-2]: ways to decode the empty prefix
var prev1 = 1 // dp[i-1]: ways to decode the first character (already known valid)
for i in 2...n {
var current = 0
if chars[i - 1] != "0" {
current += prev1 // the single digit at position i-1 is a valid one-letter code
}
let twoDigit = (chars[i - 2].wholeNumberValue ?? 0) * 10 + (chars[i - 1].wholeNumberValue ?? 0)
if twoDigit >= 10 && twoDigit <= 26 {
current += prev2 // the two digits at i-2, i-1 form a valid two-letter code
}
prev2 = prev1
prev1 = current
}
return prev1
}
// smoke test — same cases as the brute force
print(numDecodings("12")) // 2
print(numDecodings("226")) // 3
print(numDecodings("06")) // 0Big-O: O(n) time — one forward pass over the string, O(1) work per position. O(1) extra space — two rolling variables, no recursion stack.
Both versions branch on the exact same two decisions at every position — decode one digit, or decode two — but the brute force re-derives "how many ways to finish from here?" independently every time a position is reached, and because "one digit" from position i and "two digits" from position i-1 can both land on position i+1, the same suffix gets fully re-solved from multiple directions. The optimal version tabulates the other direction: "how many ways to decode everything up through position i?" is computed once per position and carried forward as prev1, ready to be reused (not re-derived) by both the one-digit and two-digit branches at every later position. Since the recurrence only ever looks back two positions, that tabulation needs just two rolling variables — the exponential re-derivation collapses into a single linear sweep.
-
1D Dynamic Programming — the recurrence
dp[i] = (valid one-digit ? dp[i-1] : 0) + (valid two-digit ? dp[i-2] : 0)is the counting-with-a-validity-gate variant of chapter 26's fixed-two-state lookback. -
Arrays and Strings —
Array(s)gives O(1) indexed character access, which both the recursive and tabulated versions rely on to inspect one- and two-digit slices.
Decode Ways is Climbing Stairs with a validity check bolted on — each step forward is either "take one digit" (if it isn't a leading zero) or "take two digits" (if that pair falls between 10 and 26), and the counts from both valid moves add together.
- Why does
numDecodingsguardchars[0] != "0"up front and return0immediately, rather than letting the loop'schars[i - 1] != "0"check handle it naturally? - Trace
numDecodings("226")by hand: what areprev1andprev2after each loop iteration, and which three decodings does the final count of3correspond to? - For a string like
"100", both digits after the leading1include a'0'. Trace through whynumDecodings("100")returns0, and identify exactly which position makes both the one-digit and two-digit branches fail simultaneously.