Сложность: 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 var memo: [[Int]] = []
private var text1: [Character] = []
private var text2: [Character] = []
func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
self.text1 = Array(text1)
self.text2 = Array(text2)
self.memo = Array(repeating: Array(repeating: -1, count: text2.count + 1), count: text1.count + 1)
return memoSolve(0, 0)
}
private func memoSolve(_ p1: Int, _ p2: Int) -> Int {
if p1 == text1.count || p2 == text2.count {
return 0
}
if memo[p1][p2] != -1 {
return memo[p1][p2]
}
var answer = 0
if text1[p1] == text2[p2] {
answer = 1 + memoSolve(p1 + 1, p2 + 1)
} else {
answer = max(memoSolve(p1, p2 + 1), memoSolve(p1 + 1, p2))
}
memo[p1][p2] = answer
return answer
}
}Ставь 👍 и забирай 📚 Базу знаний