验证回文字符串 Ⅱ
680. 验证回文字符串 Ⅱ
给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: s = "aba" 输出: true
示例 2:
输入: s = "abca" 输出: true 解释: 你可以删除c字符。
示例 3:
输入: s = "abc" 输出: false
解题思路
对于判断回文字符串我们可以定义左右指针,初始时分别指向字符串的第一个字符和最后一个字符,每次判断左右指针指向的字符是否相同,如果不相同,则不是回文串;如果相同,则将左右指针都往中间移动一位,直到左右指针相遇,则字符串是回文串。
在这题里面,我们根据这个思路,当遇到不匹配的两个字符时,我们可以尝试两个字符都删除一次以后,遍历剩余的字符串查看是否能组成回文字符串,如果还是不行,说明删除一个字符并不能使得字符串变为回文
代码
class Solution { public boolean validPalindrome(String s) { int l=0,n=s.length(),r=n-1; while(l<r) { if(s.charAt(l)!=s.charAt(r)) { return toVlidPalindrome(s,l+1,r)||toVlidPalindrome(s,l,r-1); } r--; l++; } return true; } public boolean toVlidPalindrome(String s,int l,int r) { while(l<r) { if(s.charAt(l)!=s.charAt(r)) return false; l++; r--; } return true; } } 复制代码
时间复杂度:O(n),其中 n 是字符串的长度。判断整个字符串是否是回文字符串的时间复杂度是 O(n),遇到不同字符时,判断两个子串是否是回文字符串的时间复杂度也都是 O(n)。
空间复杂度:O(1)。只需要维护有限的常量空间。
作者:Gogo472
链接:https://juejin.cn/post/7022834584005902373