Сложность: hard
Дана строка s. Вы можете преобразовать s в палиндром, добавив символы в начало строки.
Верните самый короткий палиндром, который можно получить, выполняя это преобразование.
Пример:
Input: s = "aacecaaa"
Output: "aaacecaaa"
👨💻 Алгоритм:
1⃣Создание обратной строки:
Создайте обратную строку rev от исходной строки s, чтобы использовать её для сравнения.
2⃣Итерация для поиска наибольшего палиндрома:
Перебирайте индекс i от 0 до size(s) - 1.
Для каждой итерации проверяйте, равна ли подстрока s от начала до n - i подстроке rev от i до конца строки.
Если условие выполняется, это означает, что подстрока s от начала до n - i является палиндромом, так как rev является обратной строкой s.
3⃣Возврат результата:
Как только найден наибольший палиндром, возвращайте строку, состоящую из обратной подстроки rev от начала до i + исходная строка s.
😎 Решение:
class Solution {
public function shortestPalindrome($s) {
$n = strlen($s);
$rev = strrev($s);
for ($i = 0; $i < $n; $i++) {
if (substr($s, 0, $n - $i) == substr($rev, $i)) {
return substr($rev, 0, $i) . $s;
}
}
return "";
}
}Ставь 👍 и забирай 📚 Базу знаний