Код Senior Динамическое программирование обновлено
Число расшифровок
Условие
Цифры кодируют буквы: 1→A … 26→Z. Сколько способов расшифровать строку цифр? Ведущий ноль расшифровке не поддаётся.
Примеры
numDecodings("226") // 3
numDecodings("12") // 2
numDecodings("06") // 0
Как подойти
Фибоначчи с условиями. Вся сложность в нулях: одиночный ноль обнуляет ветку, но пара 10 или 20 валидна, а 30 уже нет. Два переменных вместо массива - стандартная свёртка памяти.
Подсказки: 2
- Переход: берём одну цифру (если не ноль) или две (если 10..26).
- Нули - главный источник ошибок: '0' сам по себе не расшифровывается, а '10' и '20' - только парой.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.