Back to DSA

Decode Ways

hard
Acceptance: 36%
Dynamic Programming

Letters A through Z are mapped to the numbers 1 through 26 respectively. Given a string of digits, count the total number of distinct ways it can be interpreted as a sequence of letters.

Examples

Example 1:
Input:s = "123"
Output:3
Explanation: Can be read as 1-2-3 (ABC), 12-3 (LC), or 1-23 (AW).
Example 2:
Input:s = "2061"
Output:1
Explanation: The only valid reading is 20-6-1 (TFA), since '06' is not a valid code.

Hints

Related Problems

House RobbermediumClimbing StairseasyLongest Increasing SubsequencemediumWord BreakmediumEdit Distancehard
00:00
class Solution {
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') return 0;
        int n = s.length();
        int prev2 = 1, prev1 = 1;
        for (int i = 1; i < n; i++) {
            int curr = 0;
            if (s.charAt(i) != '0') curr += prev1;
            int twoDigit = Integer.parseInt(s.substring(i - 1, i + 1));
            if (twoDigit >= 10 && twoDigit <= 26) curr += prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}
Time complexityO(n)
Space complexityO(1)