Сложность: medium
Сообщение, содержащее буквы от A до Z, можно закодировать в числа с использованием следующего соответствия:
- 'A' -> "1"
- 'B' -> "2"
- ...
- 'Z' -> "26"
Для декодирования закодированного сообщения все цифры должны быть сгруппированы и затем отображены обратно в буквы с использованием обратного соответствия (существует несколько способов). Например, "11106" можно представить как:
- "AAJF" с группировкой (1 1 10 6)
- "KJF" с группировкой (11 10 6)
Обратите внимание, что группировка (1 11 06) недопустима, потому что "06" не может быть преобразовано в 'F', так как "6" отличается от "06".
Для данной строки s, содержащей только цифры, верните количество способов декодирования.
Тестовые случаи сформированы таким образом, что ответ укладывается в 32-битное целое число.
Пример:
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 с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач.
😎 Решение:
var restoreIpAddresses = function (s) {
var ans = [];
function valid(s, start, length) {
return (
length == 1 ||
(s.charAt(start) != "0" &&
(length < 3 || s.substring(start, start + length) <= 255))
);
}
function helper(s, startIndex, dots, ans) {
var remainingLength = s.length - startIndex;
var remainingNumberOfIntegers = 4 - dots.length;
if (
remainingLength > remainingNumberOfIntegers * 3 ||
remainingLength < remainingNumberOfIntegers
) {
return;
}
if (dots.length == 3) {
if (valid(s, startIndex, remainingLength)) {
var temp = "";
var last = 0;
for (var dot of dots) {
temp += s.substring(last, last + dot) + ".";
last += dot;
}
temp += s.substring(startIndex);
ans.push(temp);
}
return;
}
for (
var curPos = 1;
curPos <= 3 && curPos <= remainingLength;
++curPos
) {
dots.push(curPos);
if (valid(s, startIndex, curPos)) {
helper(s, startIndex + curPos, dots, ans);
}
dots.pop();
}
}
helper(s, 0, [], ans);
return ans;
};Ставь 👍 и забирай 📚 Базу знаний