Estou tentando resolver uma questão e minha pergunta aqui épor que a minha solução não funciona?. Aqui está a pergunta e abaixo está a resposta.

Pergunta tirada do leetcode:http://oj.leetcode.com/problems/decode-ways/

Uma mensagem contendo letras de A-Z está sendo codificada para números usando o seguinte mapeamento:

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

Dada uma mensagem codificada contendo dígitos, determine o número total de maneiras de decodificá-la.

Por exemplo, dada a mensagem codificada "12", ela poderia ser decodificada como "AB" (1 2) ou "L" (12). O número de maneiras de decodificar "12" é 2.

Minha solução:

O ponto com a minha solução é retroceder e multiplicar o número de opções se uma divisão for encontrada. Por divisão, quero dizer que os dígitos podem ser interpretados de duas maneiras. Por exemplo: 11 pode ser interpretado de duas maneiras 'aa' ou 'k'.

public class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int decodings = 1;
        boolean used = false; // Signifies that the prev was already use as a decimal
        for (int index = s.length()-1 ; index > 0 ; index--) {
            char curr = s.charAt(index);
            char prev = s.charAt(index-1);
            if (curr == '0') {
                if (prev != '1' && prev != '2') {
                    return 0;
                }
                index--; // Skip prev because it is part of curr
                used = false;
            } else {
                if (prev == '1' || (prev == '2' && curr <= '6')) {
                    decodings = decodings * 2;
                    if (used) {
                        decodings = decodings - 1;
                    }
                    used = true;
                } else {
                    used = false;
                }
            }
        }
        return decodings;
    }
}

A falha está na seguinte entrada:

Input:"4757562545844617494555774581341211511296816786586787755257741178599337186486723247528324612117156948"
Output: 3274568
Expected: 589824