mapDecoding

Problem Statement: A top secret message containing uppercase letters from 'A' to 'Z' has been encoded as numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

You are an FBI agent and you need to determine the total number of ways that the message can be decoded.

Since the answer could be very large, take it modulo 10⁹ + 7.

Example

For message = "123", the output should be
solution(message) = 3.

"123" can be decoded as "ABC" (1 2 3), "LC" (12 3) or "AW" (1 23), so the total number of ways is 3.

int solution(String msg) {

    if(msg.length()==0)
    return 1;

    int mod = 1000000007;

    int n = msg.length();
    int dp[] = new int[n+1];
    int prev = Character.getNumericValue(msg.charAt(0));
    dp[0] = 1;
    dp[1] = prev==0? 0 : 1;

    for(int i=2; i<n+1; i++) {        
        int curr = Character.getNumericValue(msg.charAt(i-1));
        // if the current digit is not zero        
        if(curr!=0)
            dp[i] = (dp[i] + dp[i-1])%mod;
        // check if we can form a valid number from prev and curr digit
        int num = prev*10 + curr;
        if(num>=10 && num<=26) {
            dp[i] = (dp[i] + dp[i-2])%mod;
        }
        // if no valid decoding is possible, return 0
        if(dp[i]==0)
            return 0;        
        prev = curr;
    }
    return dp[n];

}