Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Dynamic programming

Ways to decode a string of digits

Medium · Target 20 minutes · Dynamic programming · Type asked atMetaAmazonGoogle

A message of letters was encoded with A → 1, B → 2, …, Z → 26 and the numbers written one after another. Given the digit string s, return the number of ways to decode it. A code may not have a leading zero: "06" is not "F", and "0" alone decodes to nothing.

Examples

InputOutputWhy
s = "12"2"AB" (1, 2) or "L" (12).
s = "226"32 2 6, 22 6, 2 26.
s = "06"0A leading zero makes the whole string undecodable.

Constraints

  • 1 ≤ s.length ≤ 100
  • s contains only digits

Hints

Hint 1

ways[i] = number of decodings of s[i:]. ways[n] = 1 (the empty suffix).

Hint 2

Take one digit if it is not 0; take two if they form 10..26.

Hint 3

Only the next two entries are read: keep two variables.

Where people lose marks

  • Treating "0" as a valid single code.
  • Accepting "05" as a two-digit code.
  • Accepting 27 or above as two digits.
Console⌘/Ctrl + Enter runs

Write a solution and run it against the real test table.


Keep going

Preparing for a real process? Quant interview preparation, or book a free 20-minute call.