We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
A message containing letters from A-Z can be encoded into numbers using the following mapping:
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways).
Given a string s containing only digits, return the number of ways to decode it.
The test cases are generated so that the answer fits in a 32-bit integer.
A medium dynamic programming problem, graded against 8 test cases (5 of them hidden).
Overlapping subproblems solved once and reused - the pattern candidates fear most.
Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.
More Dynamic Programming problems →dp[i] = number of ways to decode the substring s[0..i-1]. For each position, check if the single digit is valid (1-9) and if the two-digit number is valid (10-26).
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
These apply to the pattern as a whole, not just this problem.