Задача: 44. Wildcard Matching
Сложность: 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)].

😎 Решение:

function isMatch($s, $p) {
    $dp = [];

    function removeDuplicateStars($p) {
        $newString = "";
        for ($i = 0; $i < strlen($p); $i++) {
            if ($newString === "" || $p[$i] !== "*") {
                $newString .= $p[$i];
            } elseif ($newString[strlen($newString) - 1] !== "*") {
                $newString .= $p[$i];
            }
        }
        return $newString;
    }

    function helper($si, $pi, $s, $p, &$dp) {
        $key = $si . "," . $pi;
        if (array_key_exists($key, $dp)) {
            return $dp[$key];
        }

        if ($pi == strlen($p)) {
            $dp[$key] = $si == strlen($s);
        } elseif ($si == strlen($s)) {
            $dp[$key] = $pi + 1 == strlen($p) && $p[$pi] == "*";
        } elseif ($p[$pi] == $s[$si] || $p[$pi] == "?") {
            $dp[$key] = helper($si + 1, $pi + 1, $s, $p, $dp);
        } elseif ($p[$pi] == "*") {
            $dp[$key] = helper($si, $pi + 1, $s, $p, $dp) || helper($si + 1, $pi, $s, $p, $dp);
        } else {
            $dp[$key] = false;
        }
        return $dp[$key];
    }

    $p = removeDuplicateStars($p);
    return helper(0, 0, $s, $p, $dp);
}

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