Сложность: medium
Даны строки s1, s2 и s3. Необходимо определить, может ли строка s3 быть сформирована путем чередования строк s1 и s2.
Чередование двух строк s и t — это конфигурация, при которой s и t делятся на n и m подстрок соответственно так, что:
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| ≤ 1
Чередование может быть таким: s1 + t1 + s2 + t2 + s3 + t3 + ... или t1 + s1 + t2 + s2 + t3 + s3 + ...
Примечание: a + b означает конкатенацию строк a и b.
Пример:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".
👨💻 Алгоритм:
1⃣В рекурсивном подходе, описанном выше, рассматривается каждая возможная строка, образованная путем чередования двух заданных строк. Однако возникают случаи, когда та же часть s1 и s2 уже была обработана, но в разных порядках (перестановках). Независимо от порядка обработки, если результирующая строка до этого момента совпадает с требуемой строкой (s3), окончательный результат зависит только от оставшихся частей s1 и s2, а не от уже обработанной части. Таким образом, рекурсивный подход приводит к избыточным вычислениям.
2⃣Эту избыточность можно устранить, используя мемоизацию вместе с рекурсией. Для этого мы поддерживаем три указателя i, j, k, которые соответствуют индексу текущего символа s1, s2, s3 соответственно. Также мы поддерживаем двумерный массив memo для отслеживания обработанных до сих пор подстрок. memo[i][j] хранит 1/0 или -1 в зависимости от того, была ли текущая часть строк, то есть до i-го индекса для s1 и до j-го индекса для s2, уже оценена. Мы начинаем с выбора текущего символа s1 (на который указывает i). Если он совпадает с текущим символом s3 (на который указывает k), мы включаем его в обработанную строку и вызываем ту же функцию рекурсивно как: is_Interleave(s1, i+1, s2, j, s3, k+1, memo).
3⃣Таким образом, мы вызвали функцию, увеличив указатели i и k, поскольку часть строк до этих индексов уже была обработана. Аналогично, мы выбираем один символ из второй строки и продолжаем. Рекурсивная функция заканчивается, когда одна из двух строк s1 или s2 полностью обработана. Если, скажем, строка s1 полностью обработана, мы напрямую сравниваем оставшуюся часть s2 с оставшейся частью s3. Когда происходит возврат из рекурсивных вызовов, мы сохраняем значение, возвращенное рекурсивными функциями, в массиве мемоизации memo соответственно, так что когда оно встречается в следующий раз, рекурсивная функция не будет вызвана, но сам массив мемоизации вернет предыдущий сгенерированный результат.
😎 Решение:
class Solution {
function isInterleave($s1, $s2, $s3) {
if (strlen($s3) != strlen($s1) + strlen($s2)) {
return false;
}
$dp = array_fill(0, strlen($s1) + 1, array_fill(0, strlen($s2) + 1, false));
for ($i = 0; $i <= strlen($s1); $i++) {
for ($j = 0; $j <= strlen($s2); $j++) {
if ($i == 0 && $j == 0) {
$dp[$i][$j] = true;
} elseif ($i == 0) {
$dp[$i][$j] = $dp[$i][$j - 1] && $s2[$j - 1] == $s3[$i + $j - 1];
} elseif ($j == 0) {
$dp[$i][$j] = $dp[$i - 1][$j] && $s1[$i - 1] == $s3[$i + $j - 1];
} else {
$dp[$i][$j] = ($dp[$i - 1][$j] && $s1[$i - 1] == $s3[$i + $j - 1]) ||
($dp[$i][$j - 1] && $s2[$j - 1] == $s3[$i + $j - 1]);
}
}
}
return $dp[strlen($s1)][strlen($s2)];
}
}Ставь 👍 и забирай 📚 Базу знаний