A message containing letters A-Z is encoded where 'A' = 1, 'B' = 2, ..., 'Z' = 26. Given a string s of digits, count how many ways you can decode it. Google asks this DP classic to assess your ability to handle overlapping subproblems with string parsing.
For s = "226", there are decodings: "BZ" (, ), "VF" (, ), and "BBF" (, , ).
Some strings have zero decodings. "06" can't be decoded because 0 doesn't map to any letter and 06 isn't valid either. Think about how 0 affects your counting.
Constraints: . s contains only digits.