Problem Statement

A message containing letters from A-Z is being encoded to numbers using the following mapping:

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

Given an encoded message containing digits, determine the total number of ways to decode it.

Solution Explanation

We can use a typical DP solution where we keep track the number of ways a string can be decoded at each character index, calculate the next index value based on the previous ones.

Below is the java implementation of the dp approach,

public class DecodeWays {

	public static void main(String[] args) {
		String s = "12345";
		System.out.println(numDecodings(s));
	}

	public static int numDecodings(String s) {
		int n = s.length();
		int[] dp = new int[n + 1];
		dp[0] = 1;
		dp[1] = s.charAt(1) != '0' ? 1 : 0;
		for (int i = 2; i <= s.length(); i++) {
			int first = Integer.parseInt(s.substring(i - 1, i));
			int second = Integer.parseInt(s.substring(i - 2, i));
			if (first >= 0 && first <= 9) {
				dp[i] += dp[i - 1];
			}
			if (second >= 10 && second <= 26) {
				dp[i] += dp[i - 2];
			}
		}

		return dp[n];
	}

}

Time Complexity

As you see, we do only one pass of the input string, so the time complexity is O(n).