680. 验证回文字符串 Ⅱ

Posted on | In
Words count in article: 193 | Reading time ≈ 1

题目

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

示例1：

1
2
输入: "aba"
输出: True

示例2：

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

示例3：

1
2
输入: s = "abc"
输出: false

提示：

  • 1 <= s.length <= 105
  • s 由小写英文字母组成

解法

解法一：

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean validPalindrome(String s) {
    for(int i = 0, j = s.length()-1; i < j ; i++, j--){
        if(s.charAt(i) != s.charAt(j)){
            //分两种情况，一是右边减一，二是左边加一
            return isPalindrome(s,i,j-1) || isPalindrome(s, i+1, j);
        }
    }
    return true;
}

public boolean isPalindrome(String s, int i, int j) {
    while (i < j) {
        if (s.charAt(i++) != s.charAt(j--)) {
            return false;
        }
    }
    return true;
}
0%