Revisar una respuesta - Decodificar maneras
Estoy tratando de resolver una pregunta y mi pregunta aquí es¿Por qué no funciona mi solución?. Aquí está la pregunta y debajo está la respuesta.
Pregunta tomada de leetcode:http://oj.leetcode.com/problems/decode-ways/
Un mensaje que contiene letras de A-Z se está codificando en números utilizando la siguiente asignación:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Dado un mensaje codificado que contiene dígitos, determine el número total de formas para decodificarlo.
Por ejemplo, dado el mensaje codificado "12", podría decodificarse como "AB" (1 2) o "L" (12). El número de formas de decodificación "12" es 2.
Mi solución:
El punto con mi solución es ir hacia atrás y multiplicar el número de opciones si se encuentra una división. Por división me refiero a que los dígitos se pueden interpretar de dos maneras. Por ejemplo: 11 puede interpretarse de dos maneras 'aa' o '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;
}
}
El fallo está en la siguiente entrada:
Input:"4757562545844617494555774581341211511296816786586787755257741178599337186486723247528324612117156948"
Output: 3274568
Expected: 589824