0%

验证回文字符串 Ⅱ

发表于 更新于 分类于

680. 验证回文字符串 Ⅱ [简单]

题目说明

Leetcode题目链接

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

解题思路

双指针

使用双指针 left right , 从字符串两端向中间遍历并一一比较。找到第一对不同的字符，分别尝试删除再比较是否回文串。

  • 时间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
private:
    bool find_diff(const string& s, int& left, int& right)
    {
        while (left < right)
        {
            if (s[left] != s[right])
            {
                return true;
            }
            left++;
            right--;
        }
        return false;
    }
public:
    bool validPalindrome(string s) {
        int left = 0;
        int right = s.size() - 1;

        while (left < right)
        {
            if (find_diff(s, left, right))
            {
                int temp_left = left + 1;
                int temp_right = right;
                if (!find_diff(s, temp_left, temp_right))
                {
                    return true;
                }

                temp_left = left;
                temp_right = right - 1;
                return !find_diff(s, temp_left, temp_right);
            }
        }

        return true;
    }
};