剑指 Offer II 019. 最多删除一个字符得到回文

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

题目

给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

示例1：

1
2
输入: s = "aba"
输出: true

示例2：

1
2
3
输入: s = "abca"
输出: true
解释: 可以删除 "c" 字符 或者 "b" 字符

示例3：

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

提示：

  • 1 <= s.length <= 10^5
  • 字符串 s 由 ASCII 字符组成

解法一：

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 validPalindrome(String s) {
        int low = 0;
        int high = s.length() - 1;
        while (low < high) {
            char c1 = s.charAt(low), c2 = s.charAt(high);
            if (c1 == c2) {
                ++low;
                --high;
            } else {
                return validPalindrome(s, low, high - 1) || validPalindrome(s, low + 1, high);
            }
        }
        return true;
    }

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