Задача: 1143. Longest Common Subsequence Сложность: medium Даны две строки text1 и text2. Верните длину их наибольшей общей подпоследовательности. Если общей подпоследовательности нет, верните 0. Подпоследовательность строки — это новая строка, созданная из оригинальной строки путем удаления некоторых символов (может быть ни одного) без изменения относительного порядка оставшихся символов. Например, "ace" является подпоследовательностью "abcde". Общая подпоследовательность двух строк — это подпоследовательность, которая является общей для обеих строк. Пример: Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3. 👨‍💻 Алгоритм: 1⃣Создайте двумерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Инициализируйте массив значением -1, чтобы указать, что эти ячейки еще не были рассчитаны. 2⃣Реализуйте рекурсивную функцию memoSolve, которая принимает два указателя на текущие позиции в text1 и text2 и возвращает длину наибольшей общей подпоследовательности для этих подстрок. Если текущие символы совпадают, добавьте 1 к результату рекурсивного вызова для следующих символов. Если не совпадают, найдите максимум между рекурсивными вызовами с измененными указателями. 3⃣Возвращайте значение memoSolve(0, 0), чтобы получить результат для всей строки. 😎 Решение: class Solution { private $memo = []; private $text1; private $text2; function longestCommonSubsequence($text1, $text2) { $this->text1 = $text1; $this->text2 = $text2; $len1 = strlen($text1); $len2 = strlen($text2); $this->memo = array_fill(0, $len1 + 1, array_fill(0, $len2 + 1, -1)); return $this->memoSolve(0, 0); } private function memoSolve($p1, $p2) { if ($p1 == strlen($this->text1) || $p2 == strlen($this->text2)) return 0; if ($this->memo[$p1][$p2] != -1) return $this->memo[$p1][$p2]; if ($this->text1[$p1] == $this->text2[$p2]) { $this->memo[$p1][$p2] = 1 + $this->memoSolve($p1 + 1, $p2 + 1); } else { $this->memo[$p1][$p2] = max($this->memoSolve($p1, $p2 + 1), $this->memoSolve($p1 + 1, $p2)); } return $this->memo[$p1][$p2]; } } Ставь 👍 и забирай 📚 Базу знаний