Различные подходы к решению Leetcode 680 в JavaScript

Палиндром — увлекательная концепция. Красота заключается в ее простоте: слово, фраза или последовательность символов, которые читаются одинаково как в прямом, так и в обратном направлении. Однако что произойдет, если мы внесем небольшое изменение в это классическое определение? Что, если мы позволим удалить не более одного символа из строки, чтобы сделать ее палиндромом? В этой статье мы рассмотрим эту интригующую проблему. Итак, садитесь поудобнее, возьмите чашку кофе и давайте окунемся в мир удаления палиндромов!

Постановка проблемы:

Учитывая строку s, вернуть true еслиsможет быть палиндромом после удаления из него не более одного символа.

Подход 1: грубая сила

Таким образом, идея состоит в том, чтобы сгенерировать все возможные подстроки, удаляя по одному символу из заданной строки и проверяя, являются ли какие-либо из подстрок палиндромами.

  1. Базовый вариант: проверьте, является ли заданная входная строка палиндромом или нет.
  2. После этого переберите входную строку и сгенерируйте все возможные подстроки, удаляя по одному символу за раз.
  3. Проверить, является ли подстрока палиндромом, если да, вернуть True. В противном случае продолжите итерацию.
  4. Если ни одна из подстрок не является палиндромом, верните 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: два указателя

  1. В этом подходе мы инициализируем два указателя, один указывает на начало строки, а другой указывает на конец строки, и сравниваем символы в этих указателях.
  2. Если символы совпадают, мы увеличиваем левый указатель и уменьшаем правый указатель.
  3. Если они не совпадают, мы можем проверить, приведет ли удаление символа к левому или правому указателю к палиндрому.
  4. Если любая из этих новых строк является палиндромом, мы можем вернуть true.
  5. В противном случае продолжаем проверять символы по указателям, пока не проверим все возможные комбинации.
// 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