Просмотрите ответ - Decode Ways

Я пытаюсь решить вопрос, и мой вопрос здесьпочему мое решение не работает?, Вот вопрос, а ниже ответ.

Вопрос взят из leetcode:http://oj.leetcode.com/problems/decode-ways/

Сообщение, содержащее буквы от A-Z, кодируется в числа с использованием следующего сопоставления:

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

Учитывая закодированное сообщение, содержащее цифры, определите общее количество способов его декодирования.

Например, учитывая закодированное сообщение «12», оно может быть декодировано как «AB» (1 2) или «L» (12). Количество способов декодирования «12» составляет 2.

Мое решение:

Суть моего решения - вернуться назад и умножить количество вариантов, если будет найдено разделение. Под разделением я подразумеваю, что цифры можно интерпретировать двумя способами. Например: 11 можно интерпретировать двумя способами: «аа» или «к».

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;
    }
}

Ошибка на следующем входе:

Input:"4757562545844617494555774581341211511296816786586787755257741178599337186486723247528324612117156948"
Output: 3274568
Expected: 589824

Ответы на вопрос(5)

Ваш ответ на вопрос