leetcode-680. 验证回文字符串 Ⅱ

本文主要是介绍leetcode-680. 验证回文字符串 Ⅱ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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

示例 1:

输入: "aba"
输出: True

示例 2:

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

注意:

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

解题思路

左右指针向中间扫描，如果不匹配，则要么删除左边的字符，要么删除右边的字符，再对删除字符后的剩下的字符串递归即可。时间复杂度是o(n)

成绩

时间>34.38%
空间>31.25%

代码

class Solution(object):def validPalindrome(self, s):""":type s: str:rtype: bool"""def is_palindrome(s, delete_flag = False):left, right = 0, len(s) - 1while left <= right:if s[left] == s[right]:left += 1right -= 1elif not delete_flag:return is_palindrome(s[left + 1:right+1], True) or is_palindrome(s[left: right], True)else:return Falsereturn Truereturn is_palindrome(s, False)

这篇关于leetcode-680. 验证回文字符串 Ⅱ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---