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

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.

Recognition Cues

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

Diagram

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

Loading diagram…

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;
}