Сложность: hard
Дана строка s. Вы можете преобразовать s в палиндром, добавив символы в начало строки.
Верните самый короткий палиндром, который можно получить, выполняя это преобразование.
Пример:
Input: s = "aacecaaa"
Output: "aaacecaaa"
👨💻 Алгоритм:
1⃣Создание обратной строки:
Создаем обратную строку rev от исходной строки s.
2⃣Итерация для поиска наибольшего палиндрома:
Перемещаемся по индексу i от 0 до n - 1.
Проверяем, является ли подстрока s от 0 до n - i равной подстроке rev от i до конца строки.
Если находим такое совпадение, возвращаем обратную подстроку от начала rev до i + исходная строка s.
3⃣Возврат результата:
Возвращаем наименьший палиндром, полученный путем добавления символов в начало строки s.
😎 Решение:
class Solution {
func shortestPalindrome(_ s: String) -> String {
let n = s.count
let rev = String(s.reversed())
for i in 0..<n {
let startIndex = s.index(s.startIndex, offsetBy: 0)
let endIndex = s.index(s.startIndex, offsetBy: n - i)
let revStartIndex = rev.index(rev.startIndex, offsetBy: i)
let revEndIndex = rev.endIndex
if s[startIndex..<endIndex] == rev[revStartIndex..<revEndIndex] {
let prefix = rev[rev.startIndex..<revStartIndex]
return prefix + s
}
}
return ""
}
}Ставь 👍 и забирай 📚 Базу знаний