Сложность: 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 String shortestPalindrome(String s) {
int n = s.length();
String rev = new StringBuilder(s).reverse().toString();
for (int i = 0; i < n; i++) {
if (s.substring(0, n - i).equals(rev.substring(i))) return (
rev.substring(0, i) + s
);
}
return "";
}
}Ставь 👍 и забирай 📚 Базу знаний