680. Valid Palindrome II

Задача

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

Примеры

Пример 1

Input: s = "aba"
Output: true

Пример 2

Input: s = "abca"
Output: true

Пояснение

Можно удалить символ ‘c’.

Пример 3

Input: s = "abc"
Output: false

Решение

Решение

/**
 * Временная сложность: O(n)
 * Пространственная сложность: O(1)
 */
function validPalindrome(s) {
    // вспомогательная функция для проверки палиндрома в диапазоне
    function isPalindromeRange(str, l, r) {
        while (l < r) {
            if (str[l] !== str[r]) return false;
            l++;
            r--;
        }
        return true;
    }
 
    let left = 0;
    let right = s.length - 1;
 
    while (left < right) {
        if (s[left] === s[right]) {
            left++;
            right--;
        } else {
            // при первом несовпадении проверяем два варианта
            return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
        }
    }
 
    return true;
}

Решение 2 (Recursive)

/**
 * Временная сложность: O(n)
 * Пространственная сложность: O(n) из-за стека вызовов
 */
function validPalindrome(s) {
    function helper(l, r, deletedOnce) {
        while (l < r) {
            if (s[l] === s[r]) {
                l++;
                r--;
            } else {
                // если уже удалили один символ, дальше нельзя
                if (deletedOnce) return false;
                // пробуем удалить левый ИЛИ правый символ
                return helper(l + 1, r, true) || helper(l, r - 1, true);
            }
        }
        return true;
    }
 
    return helper(0, s.length - 1, false);
}

Решение 3 (Split + Reverse)

/**
 * Временная сложность: O(n²) 
 * Пространственная сложность: O(n)
 */
function validPalindrome(s) {
    function isPalindrome(str) {
        return str === str.split('').reverse().join('');
    }
 
    if (isPalindrome(s)) return true;
 
    for (let i = 0; i < s.length; i++) {
        const newStr = s.slice(0, i) + s.slice(i + 1);
        if (isPalindrome(newStr)) return true;
    }
 
    return false;
}