количество способов декодировать строку?

Question

Я работаю над проблемой, когда мне нужно декодировать строку.

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

'A'-> 1

' B '-> 2

...

' Z '-> 26

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

Пример 1:

Ввод: "12"

Выход: 2

Объяснение:Он может быть декодирован как «AB» (1 2) или «L» (12).

Пример 2:

Вход: «226»

Выход: 3

Объяснение: Он может быть декодирован как "BZ" (2 26), "VF" (22 6) или "BBF" (2 2 6).

Я подошелс подходом ниже рекурсии, но это дает неправильный вывод для этого входа "227".Выходные данные должны быть «2», но моя программа выдает «3»:

  public static int decodeWays(String data) {
    return helper(data, data.length());
  }

  private static int helper(String data, int k) {
    if (k == 0)
      return 1;
    int s = data.length() - k;
    if (data.charAt(s) == '0')
      return 0;

    int result = helper(data, k - 1);
    if (k >= 2 && Integer.parseInt(data.substring(0, 2)) <= 26) {
      result += helper(data, k - 2);
    }
    return result;
  }

Что не так с моим подходом?

Answer 1

В этой строке -

if (k >= 2 && Integer.parseInt(data.substring(0, 2)) <= 26) {

Вы всегда проверяете одно и то же двузначное число data.substring(0, 2).Вместо этого рассмотрим что-то вроде

data.substring(data.length()-k, data.length()).substring(0, 2)

или

data.substring(data.length()-k, data.length()-k+2)