680. Valid Palindrome II

Problem

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

https://leetcode.cn/problems/valid-palindrome-ii/

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.

Test Cases

1 2	class Solution: def validPalindrome(self, s: str) -> bool:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('s, expected', [
    ("aba", True),
    ("abca", True),
    ("abc", False),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, s, expected):
    assert sol.validPalindrome(s) == expected

Thoughts

125. Valid Palindrome 的进阶版，这次允许删除最多一个字符（同时去掉了大小写转换和特殊字符的处理）。

依然从两头向中间扫描。当扫描过程中遇到 s[i] ≠ s[j] 的情况，要么删除位置 i 的字符，要么删除位置 j 的字符。即检查 s[i+1...j] 或 s[i...j+1] 是否是回文，如果都不是，则结果为 false。

时间复杂度 O(n)，空间复杂度 O(1)。

Code

solution.py

class Solution:
    def validPalindrome(self, s: str) -> bool:
        i = 0
        j = len(s) - 1
        while i < j:
            if s[i] != s[j]:
                return self.is_palindrome(s, i + 1, j) or self.is_palindrome(s, i, j - 1)
            i += 1
            j -= 1

        return True

    def is_palindrome(self, s: str, i: int, j: int) -> bool:
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1

        return True

本文引用
- 125. Valid Palindrome

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。