Задача №91 на LeetCode — это как быть шпионом! Вам дали зашифрованное сообщение из цифр, и нужно узнать, сколькими способами его можно превратить обратно в буквы.
Условие задачи (простыми словами)
🎯 Что такое "кодирование"?
Представьте, что у вас есть секретный код, где каждой букве соответствует число:
A = 1 B = 2 C = 3 ... Z = 26
Если друг отправил вам сообщение "12", его можно расшифровать двумя способами:
Способ 1: 1 + 2 → A + B → "AB"
Способ 2: 12 → L → "L"
Ответ: 2 способа ✅
Ваша задача:
Дана строка из цифр s.
Верните количество способов, которыми можно расшифровать это сообщение.
Если сообщение нельзя расшифровать вообще → верните 0.
Примеры "на пальцах"
Пример 1: s = "12"
Вариант 1: [1][2] → A + B → "AB"
Вариант 2: [12] → L → "L"
Ответ: 2 способа ✅
Пример 2: s = "226"
Вариант 1: [2][2][6] → B + B + F → "BBF"
Вариант 2: [2][26] → B + Z → "BZ"
Вариант 3: [22][6] → V + F → "VF"
Ответ: 3 способа ✅
Как решать?
Способ: Динамическое программирование
Идея: Строим таблицу dp, где dp[i] = количество способов расшифровать первые i символов.
Формула DP:
dp[i] = dp[i-1] (если s[i-1] ≠ '0')
+ dp[i-2] (если s[i-2:i] от 10 до 26)
Код решения (DP):
Заключение
Пример, рассмотренный в статье, можно найти по адресу:
https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task91_decodeWays/Solution.java