leetcode#680-验证回文字符串

(Updated: )
数据结构与算法
,

按照题意理解即可

题目描述

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

示例 1:

输入: s = “aba”
输出: true
示例 2:

输入: s = “abca”
输出: true
解释: 你可以删除c字符。
示例 3:

输入: s = “abc”
输出: false

思路

题目中给定的条件是，最多删除一个字符，判断是不是回文串；

先正常判断s是不是回文串，然后当遇到第一对不一样的字符串时，去掉左边判断是否是回文串，再去掉右边再判断是不是回文串

如果有一个是，那就是成立的，如果去掉左边和去掉右边判断都不是回文串，那就不满足题意，返回false即可

代码

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean isPalindrome(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

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