leetcode680. 验证回文字符串 Ⅱ-双指针

leetcode680. 验证回文字符串 Ⅱ-双指针

五月 23, 2020

leetcode680. 验证回文字符串 Ⅱ

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

示例 1:
输入: “aba”
输出: True

示例 2:
输入: “abca”
输出: True
解释: 你可以删除c字符。

注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

双指针解法

头指针和尾指针一起走，一个从前往后，一个从后往前，一样就说明是满足回文，下面考虑如果不一样怎么办。
如果在不相等的时候直接在while里面比较i+1与j或者i与j-1的关系，对于这个"aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga"
就会在比较cup那里出错。所以要拆开来单独写。

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
//错误示范
class Solution {
    public boolean validPalindrome(String s) {
        int i = 0,  j = s.length() - 1;
        int flag = 0;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                if (flag == 0) {
                    flag = 1;
                    if (s.charAt(i + 1) == s.charAt(j)) {
                        i++;
                    } else if (s.charAt(i) == s.charAt(j - 1)) {
                        j--;
                    } else {
                        return false;
                    } 
                } else {
                    return false;
                }
            }
            i++;
            j--;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//正确解法
class Solution {
    public boolean validPalindrome(String s) {
        int i = 0,  j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return (subs(s,i + 1,j) || subs(s,i,j - 1));
            }
            i++;
            j--;
        }
        return true;
    }
    public boolean subs(String s,int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

leetcode 101