DSA · Dynamic Programming · #63
Decode Ways
Module 47 · difficulty 3/5·⏱ 30:00starts on first keystroke
A message containing letters `A-Z` is encoded to numbers using the 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 (there may be multiple ways). For example, `"11106"` can be decoded as `"AAJF"` (1 1 10 6) or `"KJF"` (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"`. Implement `numDecodings(s)` that returns the **number of ways** to decode the digit string `s`. The answer fits in a 32-bit integer.
Examples
s = "12"→2— "AB" (1 2) or "L" (12).s = "226"→3— "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).s = "06"→0— Leading zero cannot be mapped; "6" and "06" are different.
Constraints
- · 1 <= s.length <= 100
- · s contains only digits and may contain leading zero(s).
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.