Сложность: hard
Дана входная строка (s) и шаблон (p), реализуйте сопоставление с шаблоном с поддержкой символов '?' и '*' где:
'?' соответствует любому одиночному символу.
'*' соответствует любой последовательности символов (включая пустую последовательность).
Сопоставление должно покрывать всю входную строку (не частично).
Пример:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
👨💻 Алгоритм:
1️⃣Очистите входные данные, заменив несколько звездочек подряд одной звездочкой: p = remove_duplicate_stars(p).
Инициируйте хеш-карту для мемоизации dp.
Верните вспомогательную функцию с очищенным входом: helper(s, p).
2️⃣Функция helper(s, p):
Если пара (s, p) уже известна и сохранена в dp, верните значение.
Если строки равны (p == s) или шаблон соответствует любой строке (p == '*'), добавьте dp[(s, p)] = True.
В противном случае, если p пусто или s пусто, добавьте dp[(s, p)] = False.
Если текущие символы совпадают (p[0] == s[0] или p[0] == '?'), то сравните следующие и добавьте dp[(s, p)] = helper(s[1:], p[1:]).
3️⃣Если текущий символ шаблона - звездочка (p[0] == '*'), то возможны две ситуации: звездочка не соответствует никаким символам, и звездочка соответствует одному или нескольким символам: dp[(s, p)] = helper(s, p[1:]) или helper(s[1:], p).
Если p[0] != s[0], тогда добавьте dp[(s, p)] = False.
Когда значение вычислено, верните его: dp[(s, p)].
😎 Решение:
var isMatch = function (s, p) {
var dp = {};
var remove_duplicate_stars = function (p) {
var new_string = "";
for (var c of p) {
if (new_string.length == 0 || c != "*") new_string += c;
else if (new_string[new_string.length - 1] != "*") new_string += c;
}
return new_string;
};
var helper = function (si, pi) {
var key = si + "," + pi;
if (key in dp) return dp[key];
if (pi == p.length) dp[key] = si == s.length;
else if (si == s.length) dp[key] = pi + 1 == p.length && p[pi] == "*";
else if (p[pi] == s[si] || p[pi] == "?")
dp[key] = helper(si + 1, pi + 1);
else if (p[pi] == "*")
dp[key] = helper(si, pi + 1) || helper(si + 1, pi);
else dp[key] = false;
return dp[key];
};
p = remove_duplicate_stars(p);
return helper(0, 0);
};Ставь 👍 и забирай 📚 Базу знаний