Define dp[i] as the number of decodings for the first i digits.

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

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Decode Ways

Examples

Hints

Related Problems