Kotlin | LeetCode

Задача: 91. Decode Ways
Сложность: medium

Сообщение, содержащее только цифры, нужно декодировать в буквы от 'A' до 'Z', где 'A' → "1", 'B' → "2", ..., 'Z' → "26". Верните количество всех возможных способов декодирования строки.

Пример:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

👨‍💻

Алгоритм:

1⃣Входим в рекурсию с данной строкой, начиная с индекса 0.

2⃣Для окончательного случая рекурсии мы проверяем конец строки. Если мы достигли конца строки, возвращаем 1. Каждый раз, когда мы входим в рекурсию, это для подстроки исходной строки. Если первый символ в подстроке равен 0, то прекращаем этот путь, возвращая 0. Таким образом, этот путь не будет влиять на количество способов.

3⃣Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач.

😎

Решение:

class Solution {
    private val memo = mutableMapOf<Int, Int>()

    private fun recursiveWithMemo(index: Int, s: String): Int {
        if (index == s.length) {
            return 1
        }

        if (s[index] == '0') {
            return 0
        }

        if (index == s.length - 1) {
            return 1
        }

        memo[index]?.let {
            return it
        }

        var answer = recursiveWithMemo(index + 1, s)
        if (index < s.length - 1 && s.substring(index, index + 2).toInt() <= 26) {
            answer += recursiveWithMemo(index + 2, s)
        }

        memo[index] = answer
        return answer
    }

    fun numDecodings(s: String): Int {
        return recursiveWithMemo(0, s)
    }
}

fun main() {
    val solution = Solution()
    val s = "226"
    println("Number of ways to decode: ${solution.numDecodings(s)}")
}

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post