91. Decode Ways

At a Glance

• Topic: dp-1d
• Pattern: Dynamic Programming (string digit partition)
• Difficulty: Medium
• Companies: Google, Amazon, Facebook, Microsoft, Bloomberg
• Frequency: High
• LeetCode: 91

Problem (one-liner)

A message is encoded with A=1 … Z=26. Given a digit string s, count how many ways to decode it into valid letter sequences (no leading zeros on two-digit codes). Input: digits s. Output: count.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• “Decode ways” / mapping digits to letters 1–26
• Leading zero invalidates a split
• Partition string with 1- or 2-digit chunks

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — recurse splits — exponential.
• Better — memoized recursion — O(n) time / O(n) space.
• Optimal — bottom-up dp[index] = ways for prefix ending at index — O(n) time / O(1) space rolling. <- pick this in interview.

Optimal Solution

Go

package main

func numDecodingsTable(s string) int {
	length := len(s)
	if length == 0 || s[0] == '0' {
		return 0
	}
	dp := make([]int, length+1)
	dp[0] = 1
	dp[1] = 1
	for index := 2; index <= length; index++ {
		if s[index-1] != '0' {
			dp[index] += dp[index-1]
		}
		twoDigit := 10*(s[index-2]-'0') + (s[index-1] - '0')
		if twoDigit >= 10 && twoDigit <= 26 {
			dp[index] += dp[index-2]
		}
	}
	return dp[length]
}

func numDecodings(s string) int {
	length := len(s)
	if length == 0 || s[0] == '0' {
		return 0
	}
	previousPrevious := 1
	previous := 1
	for index := 1; index < length; index++ {
		current := 0
		if s[index] != '0' {
			current += previous
		}
		twoDigit := 10*(s[index-1]-'0') + (s[index] - '0')
		if twoDigit >= 10 && twoDigit <= 26 {
			current += previousPrevious
		}
		previousPrevious = previous
		previous = current
	}
	return previous
}

JavaScript

function numDecodingsTable(s) {
	const length = s.length;
	if (length === 0 || s[0] === '0') return 0;
	const dp = new Array(length + 1).fill(0);
	dp[0] = 1;
	dp[1] = 1;
	for (let index = 2; index <= length; index++) {
		if (s[index - 1] !== '0') {
			dp[index] += dp[index - 1];
		}
		const twoDigit =
			10 * (s.charCodeAt(index - 2) - 48) +
			(s.charCodeAt(index - 1) - 48);
		if (twoDigit >= 10 && twoDigit <= 26) {
			dp[index] += dp[index - 2];
		}
	}
	return dp[length];
}

function numDecodings(s) {
	const length = s.length;
	if (length === 0 || s[0] === '0') return 0;
	let previousPrevious = 1;
	let previous = 1;
	for (let index = 1; index < length; index++) {
		let current = 0;
		if (s[index] !== '0') {
			current += previous;
		}
		const twoDigit =
			10 * (s.charCodeAt(index - 1) - 48) +
			(s.charCodeAt(index) - 48);
		if (twoDigit >= 10 && twoDigit <= 26) {
			current += previousPrevious;
		}
		previousPrevious = previous;
		previous = current;
	}
	return previous;
}

Walkthrough

Input: s = "226"

Ways: BZ(2,26), VF(22,6), BBF(2,2,6).

Edge Cases

• "0" → 0 ways
• "10", "100" with careful carry of zeros
• "01" invalid as start

Pitfalls

• Treating "06" as valid two-digit
• Forgetting previous becomes 0 when both one- and two-digit transitions fail at a position

Similar Problems

• 139. Word Break — partition with dictionary instead of digits.
• 322. Coin Change — counting compositions with constraints.

Variants

• Print all decodings → backtracking.
• Decode with * wildcard (LeetCode 639) → extended transitions.

Mind-Map Tags

#dp-1d #string-dp #digit-partition #rolling-state #medium