Задача: 680. Valid Palindrome II
Сложность: easy

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

Пример:

Input: s = "aba"
Output: true

👨‍💻 Алгоритм:

1⃣Создайте вспомогательную функцию checkPalindrome, которая принимает строку s и два указателя i и j. Эта функция возвращает логическое значение, указывающее, является ли подстрока s.substring(i, j) палиндромом.

2⃣Инициализируйте два указателя: i = 0 и j = s.length() - 1. Пока i < j, проверьте, совпадают ли символы в индексах i и j. Если нет, это значит, что нам нужно удалить один из этих символов.

3⃣Попробуйте оба варианта, используя checkPalindrome. Верните true, если либо checkPalindrome(s, i, j - 1), либо checkPalindrome(s, i + 1, j) возвращает true. Если мы выходим из цикла while, это значит, что исходная строка является палиндромом. Поскольку нам не нужно было использовать удаление, следует вернуть true.

😎 Решение:

class Solution {
    private function checkPalindrome($s, $i, $j) {
        while ($i < $j) {
            if ($s[$i] != $s[$j]) {
                return false;
            }
            $i++;
            $j--;
        }
        return true;
    }
    
    public function validPalindrome($s) {
        $i = 0;
        $j = strlen($s) - 1;
        
        while ($i < $j) {
            if ($s[$i] != $s[$j]) {
                return $this->checkPalindrome($s, $i, $j - 1) || $this->checkPalindrome($s, $i + 1, $j);
            }
            $i++;
            $j--;
        }
        
        return true;
    }
}

Ставь 👍 и забирай 📚 Базу знаний