Сложность: hard
Дана строка s. За один шаг вы можете вставить любой символ в любой индекс строки.
Верните минимальное количество шагов, необходимых для превращения s в палиндром.
Палиндром — это строка, которая читается одинаково как вперед, так и назад.
Пример:
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.
👨💻 Алгоритм:
1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте строковую переменную sReverse и установите её значение как обратную строку s.
2⃣Создайте двумерный массив memo размером n + 1 на n + 1, где memo[i][j] будет содержать длину наибольшей общей подпоследовательности, учитывая первые i символов строки s и первые j символов строки sReverse. Инициализируйте массив значением -1.
3⃣Верните n - lcs(s, sReverse, n, n, memo), где lcs - это рекурсивный метод с четырьмя параметрами: первая строка s1, вторая строка s2, длина подстроки от начала s1, длина подстроки от начала s2 и memo. Метод возвращает длину наибольшей общей подпоследовательности в подстроках s1 и s2. В этом методе выполните следующее:
Если m == 0 или n == 0, это означает, что одна из двух подстрок пуста, поэтому верните 0.
Если memo[m][n] != -1, это означает, что мы уже решили эту подзадачу, поэтому верните memo[m][n].
Если последние символы подстрок совпадают, добавьте 1 и найдите длину наибольшей общей подпоследовательности, исключив последний символ обеих подстрок. Верните memo[i][j] = 1 + lcs(s1, s2, m - 1, n - 1, memo).
В противном случае, если последние символы не совпадают, рекурсивно найдите наибольшую общую подпоследовательность в обеих подстроках, исключив их последние символы по одному. Верните memo[i][j] = max(lcs(s1, s2, m - 1, n, memo), lcs(s1, s2, m, n - 1, memo)).
😎 Решение
class Solution {
private func lcs(_ s1: [Character], _ s2: [Character], _ m: Int, _ n: Int, _ memo: inout [[Int]]) -> Int {
if m == 0 || n == 0 {
return 0
}
if memo[m][n] != -1 {
return memo[m][n]
}
if s1[m - 1] == s2[n - 1] {
return memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, &memo)
}
return memo[m][n] = max(lcs(s1, s2, m - 1, n, &memo), lcs(s1, s2, m, n - 1, &memo))
}
func minInsertions(_ s: String) -> Int {
let n = s.count
let sReverse = String(s.reversed())
var memo = Array(repeating: Array(repeating: -1, count: n + 1), count: n + 1)
return n - lcs(Array(s), Array(sReverse), n, n, &memo)
}
}Ставь 👍 и забирай 📚 Базу знаний