A message containing letters fromA-Zis 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.

Have you met this question in a real interview?

Yes

Example

Given encoded message12, it could be decoded asAB(1 2) orL(12).
The number of ways decoding12is 2.

public class Solution {
    /**
     * @param s a string,  encoded message
     * @return an integer, the number of ways decoding
     */
    public int numDecodings(String s) {
        // Write your code here
        if (s == null || s.length() == 0) {
            return 0;
        }

        //first n
        int n = s.length();
        int[] f = new int[n + 1];
        char[] arrayS = s.toCharArray();

        //init
        f[0] = 1;
        f[1] = s.charAt(0) != '0' ? 1 : 0;


        int i;
        for (i = 2; i <= n; i++) {
            if (arrayS[i - 1] - '0' != 0) {
                f[i] = f[i - 1];
            }

            int code2 = (arrayS[i - 2] -'0') * 10 + (arrayS[i - 1] - '0');
            if (code2 <= 26 && code2 >= 10) {
                f[i] += f[i - 2];
            }
        }

        return f[n];



    }
}