LeetCode 91 · Medium · 1-D Dynamic Programming

Decode Ways

Letters were encoded as numbers, A = 1 through Z = 26, and the digits were run together. Given the digit string s, count how many ways it splits back into letters.

O(n)time
O(n)space · O(1) with 2 vars
1 or 2 digitsper letter

digits 0–9 · 1–20 characters

s the bracket is the substring being tested

dp dp[i] = ways to decode s.substring(i) · filled right to left · dp[n] = 1 (the empty tail)

public int numDecodings(String s) { int n = s.length(); int[] dp = new int[n + 1]; dp[n] = 1; for (int i = n - 1; i >= 0; i--) { if (s.charAt(i) == '0') { dp[i] = 0; } else { dp[i] = dp[i + 1]; } if (i + 1 < n && (s.charAt(i) == '1' || s.charAt(i) == '2' && s.charAt(i + 1) <= '6')) { dp[i] += dp[i + 2]; } } return dp[0];}
i
—
s.charAt(i)
—
s.substring(i, i+2)
—
dp[i]
—

Why it works

  1. Brute force tries every split into 1- and 2-digit pieces and checks each piece: up to about 1.6ⁿ splits, exponential.
  2. The first letter decides: a decoding of s.substring(i) starts with a 1-digit letter (any digit but 0), then decodes s.substring(i + 1); or with a 2-digit letter (10 to 26), then decodes s.substring(i + 2). The two groups never overlap, so dp[i] = dp[i+1] + dp[i+2], each term only when its piece is valid.
  3. Right to left, one pass: each cell reads two cells to its right, which are already final. O(n) time; the array holds n + 1 entries, and two variables would do.
  4. Pitfall: zeros. "0" alone is no letter, so dp[i] = 0 when s.charAt(i) is '0', and only "10" and "20" can absorb a zero. "06" decodes 0 ways, not 1.
  5. Base case: dp[n] = 1 counts the empty tail as one finished decoding. Without it every sum would be 0.
  6. Related: with no zeros and every pair valid this is Climbing Stairs: "1111111" gives a Fibonacci number. Decode Ways II adds a * wildcard.