Próbuję rozwiązać pytanie, a moje pytanie jest tutajdlaczego moje rozwiązanie nie działa?. Oto pytanie i odpowiedź poniżej.

Pytanie zaczerpnięte z kodu leetcode:http://oj.leetcode.com/problems/decode-ways/

Wiadomość zawierająca litery od A-Z jest kodowana do liczb przy użyciu następującego mapowania:

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

Biorąc pod uwagę zakodowaną wiadomość zawierającą cyfry, określ całkowitą liczbę sposobów jej odkodowania.

Na przykład, biorąc pod uwagę zakodowaną wiadomość „12”, można ją zdekodować jako „AB” (1 2) lub „L” (12). Liczba sposobów dekodowania „12” wynosi 2.

Moje rozwiązanie:

Punktem w moim rozwiązaniu jest cofanie się i mnożenie liczby opcji w przypadku znalezienia podziału. Przez podział rozumiem, że cyfry można interpretować na dwa sposoby. Na przykład: 11 może interpretować na dwa sposoby „aa” lub „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;
    }
}

Błąd jest następujący:

Input:"4757562545844617494555774581341211511296816786586787755257741178599337186486723247528324612117156948"
Output: 3274568
Expected: 589824