一、题目描述

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: "aba"
输出: True

示例 2:

输入: "abca"
输出: True
解释: 你可以删除c字符。

注意:

字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

二、解题思路 & 代码

双指针 + 贪心算法

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def checkPalindrome(low, high):
            i, j = low, high
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True

        low, high = 0, len(s) - 1
        while low < high:
            if s[low] == s[high]: 
                low += 1
                high -= 1
            else:
                return checkPalindrome(low + 1, high) or checkPalindrome(low, high - 1)
        return True

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串的长度。判断整个字符串是否是回文字符串的时间复杂度是 O(n)，遇到不同字符时，判断两个子串是否是回文字符串的时间复杂度也都是 O(n)。
  • 空间复杂度：O(1)。只需要维护有限的常量空间。

=================================================================

变形

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

  • 如果能，则返回删除一个字符以后的字符串
  • 如果不能，则返回 False

代码

import sys

def validPalinddrom(s):
    def checkPalindrome(low, high):
        i, j = low, high
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

    low, high = 0, len(s) - 1
    flag = False
    flag_1 = False
    flag_2 = False
    while low < high:
        if s[low] == s[high]:
            low += 1
            high -= 1
        else:
            flag = True     # 判断是否进入 else，一旦进入 else 即说明不是天生的回文字符串
            flag_1 = checkPalindrome(low + 1, high)
            flag_2 = checkPalindrome(low, high - 1)
            break           # 因为只允许删除一个，所以删除一个以后就要 break

    res = True
    if not flag:             # 无需删除任何字符即满足回文
        palindromeStr = s
    elif flag_1:             # 从左边删除一个字符
        palindromeStr = s.replace(s[low], '')  # 表示将 s[low] 删除（替换成空''）
    elif flag_2:
        palindromeStr = s.replace(s[high], '')
    elif flag and not flag_1 and not flag_2:
        res = False
        return res

    return res, palindromeStr
    #return res


if __name__ == '__main__':
    type_flag = 3
    if type_flag == 0: s = 'abcddcba'     # 无需删除
    elif type_flag == 1: s = 'ab#cddcba'  # 从左边删除一个即可
    elif type_flag == 2: s = 'abcddc#ba'  # 从右边删除一个即可
    elif type_flag == 3: s = 'abcddc##ba' # 删除一个也不行
    res = validPalinddrom(s)
    print(res)