##### 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 = 1;
dp = 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).