Различные подходы к решению Leetcode 680 в JavaScript
Палиндром — увлекательная концепция. Красота заключается в ее простоте: слово, фраза или последовательность символов, которые читаются одинаково как в прямом, так и в обратном направлении. Однако что произойдет, если мы внесем небольшое изменение в это классическое определение? Что, если мы позволим удалить не более одного символа из строки, чтобы сделать ее палиндромом? В этой статье мы рассмотрим эту интригующую проблему. Итак, садитесь поудобнее, возьмите чашку кофе и давайте окунемся в мир удаления палиндромов!
Постановка проблемы:
Учитывая строку
s
, вернутьtrue
еслиs
может быть палиндромом после удаления из него не более одного символа.
Подход 1: грубая сила
Таким образом, идея состоит в том, чтобы сгенерировать все возможные подстроки, удаляя по одному символу из заданной строки и проверяя, являются ли какие-либо из подстрок палиндромами.
- Базовый вариант: проверьте, является ли заданная входная строка палиндромом или нет.
- После этого переберите входную строку и сгенерируйте все возможные подстроки, удаляя по одному символу за раз.
- Проверить, является ли подстрока палиндромом, если да, вернуть True. В противном случае продолжите итерацию.
- Если ни одна из подстрок не является палиндромом, верните False.
// ES6 Arrow Function const validPalindrome = s => { // Base Case if (isPalindrome(s)) { return true; } // Generate all possible substrings by removing one character at a time for (let i = 0; i < s.length; i++) { let substr = s.slice(0, i) + s.slice(i + 1); // Check if the substring is a palindrome if (isPalindrome(substr)) return true; } // If none of the substrings are palindromes, return false return false; } // helper function to check if a string is a palindrome. const isPalindrome = s => { let left = 0; let right = s.length - 1; while (left < right) { if (s[left] !== s[right]) { return false; } left++; right--; } return true; }
Временная сложность:O(N³)
Пространственная сложность:O(N)
Примечание. Этот метод крайне неэффективен, поскольку мы генерируем все возможные подстроки.
Подход 2: два указателя
- В этом подходе мы инициализируем два указателя, один указывает на начало строки, а другой указывает на конец строки, и сравниваем символы в этих указателях.
- Если символы совпадают, мы увеличиваем левый указатель и уменьшаем правый указатель.
- Если они не совпадают, мы можем проверить, приведет ли удаление символа к левому или правому указателю к палиндрому.
- Если любая из этих новых строк является палиндромом, мы можем вернуть true.
- В противном случае продолжаем проверять символы по указателям, пока не проверим все возможные комбинации.
// ES6 Arrow Function const validPalindrome = s => { let left = 0, right = s.length - 1; while(left < right) { if(s[left] !== s[right]) { // check if deleting the char at the left pointer or right pointer would result in a palindrome. return isPalindrome(s.slice(left, right)) || isPalindrome(s.slice(left + 1, right + 1)); } left++; right--; } return true; } // helper function to check if a string is a palindrome. const isPalindrome = s => { let left = 0; let right = s.length - 1; while (left < right) { if (s[left] !== s[right]) { return false; } left++; right--; } return true; }
Временная сложность:O(N)
Пространственная сложность:O(N)
Подход 3: Модифицированные двух указатели
В предыдущем подходе мы использовали оператор slice()
для входной строки и передавали полученную подстроку в качестве аргумента функции isPalindrome()
, чтобы проверить, является ли подстрока палиндромом или нет. Однако этот подход приводит к линейной пространственной сложности O(N), где N — длина входной строки, поскольку новая подстрока создается на каждой итерации цикла.
Чтобы добиться постоянной пространственной сложности, мы можем изменить функцию isPalindrome()
, чтобы она принимала входную строку и начальный и конечный индексы в качестве аргументов вместо создания новой подстроки с помощью оператора slice()
. Поступая таким образом, мы можем избежать создания новых подстрок и добиться постоянной пространственной сложности O (1).
// ES6 Arrow Function const validPalindrome = s => { let left = 0; let right = s.length - 1; while (left < right) { if (s[left] !== s[right]) { return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1); } left++; right--; } return true; } // Helper function to check if a string is a palindrome or not const isPalindrome = (s, left, right) => { while (left < right) { if (s[left] !== s[right]) { return false; } left++; right--; } return true; }
Временная сложность:O(N)
Пространственная сложность:O(1)
И у вас есть это, ребята! Мы исследовали различные подходы, оптимизировали наши решения и, надеюсь, повеселились. Помните, когда дело доходит до палиндромов, иногда дело не в том, чтобы быть идеальным, а в том, чтобы быть достаточно близким. Так что не беспокойтесь, если вы не можете сделать палиндром из своей строки, просто удалите символ и на этом закончите. Ведь, как говорят в мире палиндромов, «Человек, план, канал, Панама!».
Я надеюсь, что эта статья предоставила вам ценную информацию и помогла лучше понять различные подходы к решению этой проблемы. Удачного кодирования!
Проблема - Литкод 680