Decode Ways
Medium · Dynamic Programming · about 20 minutes
Asked at Meta, Google, Microsoft, Uber.
Letters were turned into numbers using A = 1, B = 2, …, Z = 26, and the numbers were written next to each other without separators. Given such a digit string s, count how many letter strings could have produced it. A 0 is only valid as the second digit of 10 or 20, and a code can't start with a 0 (so "06" is not a letter).