Сложность: medium
Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.
Строка s соответствует шаблону, если существует биективное отображение отдельных символов на непустые строки так, что если каждый символ в шаблоне заменить на строку, которой он отображается, то результирующая строка будет равна s. Биективное отображение означает, что ни два символа не отображаются на одну и ту же строку, и ни один символ не отображается на две разные строки.
Пример:
Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"
👨💻 Алгоритм:
1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.
2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.
3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `
😎 Решение:
class Solution {
function wordPatternMatch($pattern, $s) {
$symbolMap = [];
$wordSet = [];
return $this->isMatch($s, 0, $pattern, 0, $symbolMap, $wordSet);
}
private function isMatch($s, $sIndex, $pattern, $pIndex, &$symbolMap, &$wordSet) {
if ($pIndex == strlen($pattern)) {
return $sIndex == strlen($s);
}
$symbol = $pattern[$pIndex];
if (isset($symbolMap[$symbol])) {
$word = $symbolMap[$symbol];
if (substr($s, $sIndex, strlen($word)) !== $word) {
return false;
}
return $this->isMatch($s, $sIndex + strlen($word), $pattern, $pIndex + 1, $symbolMap, $wordSet);
}
for ($k = $sIndex + 1; $k <= strlen($s); $k++) {
$newWord = substr($s, $sIndex, $k - $sIndex);
if (in_array($newWord, $wordSet)) {
continue;
}
$symbolMap[$symbol] = $newWord;
$wordSet[] = $newWord;
if ($this->isMatch($s, $k, $pattern, $pIndex + 1, $symbolMap, $wordSet)) {
return true;
}
unset($symbolMap[$symbol]);
array_pop($wordSet);
}
return false;
}
}
?>Ставь 👍 и забирай 📚 Базу знаний