【leetcode】 最多删除一个字符得到回文

一、题目描述

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

二、代码思路

首先，循环剔除字符。

其次，将剔除字符后的字符串传入函数，判断是否回文串。

2.2 思路2：

分析超时的原因：

首先，我们一次循环遍历才能判断是不是回文串，这是没有办法优化的。

其次，我们需要外套一层循环来剔除单个字符，时间开销就来自于这里，我们每次剔除字符都会使用：
StringBuffer str = new StringBuffer();

str = new StringBuffer(s.substring(i + 1,length));

append(s.substring(i + 1, length));

这些操作时间开销：1、创建对象。 2、截取字符串也会创建对象。3、append字符串也会造成时间开销。

所以如果我们放弃剔除字符创建新的对象这样的操作，而是遍历的时候跳过那个字符不就减少了时间开销吗？

1 次 for 循环遍历即可，使用双指针，遇到需要剔除的元素就跳过。还是超时

2.3 思路3

创建对象的开销去除之后，还是超时，看来只能降低到一次for循环。

参考leetcode官方题解：

三、代码题解

class Solution {
    private boolean isPalindrome(int length, int dist, StringBuffer str) {
        for(int i = length / 2 - 1;i >= 0; i--) {
            if(str.charAt(i) != str.charAt(i + dist)) return false;
            dist += 2;
        }
        return true;
    }
    public boolean validPalindrome(String s) {
        int length = s.length();
        if(length == 1 || length == 2) return true;
        boolean res = false;
        for(int i = 0; i < length; i++) {
            StringBuffer str = new StringBuffer();
            //删一个元素
            if(i == 0) {
                str = new StringBuffer(s.substring(i + 1,length));
                //System.out.println(s.substring(1,length));
            } 
            else {
                str = new StringBuffer(s.substring(0, i)).append(s.substring(i + 1, length)); 
            }
            //开始判断回文串
            
            res = (length - 1) % 2 == 0 ? 
                    isPalindrome(length - 1, 1, str) : isPalindrome(length - 1, 2, str);
            if(res == true) return res; 
        }
        return false;                
    }
}
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

时间复杂度： O(n2)
s.length < 10^5
显然 10^10 会超时

class Solution {
    private boolean isPalindrome(int length, String str, int j) {
        //使用双指针来判断，从中间到两边来遍历，不太容易
        int l = 0;
        int r = length - 1;
        while(l < r){
            //由于我已经对长度为 1 和 2 的字符串做了判断，
            //所以下面的操作 l 永远不可能大于 r 所以 while 循环不用再加判断条件
            if(l == j) l++;
            if(r == j) r--;
            if(str.charAt(l) != str.charAt(r)) {
                return false; 
            }else {
                l++;
                r--;
            }
        }
        return true;
    }
    public boolean validPalindrome(String s) {
        int length = s.length();
        if(length == 1 || length == 2) return true;
        boolean res = false;
        for(int i = 0; i < length; i++) {
            //开始判断回文串
            res = (length - 1) % 2 == 0 ? 
                    isPalindrome(length, s, i) : isPalindrome(length, s, i);
            if(res == true) return res; 
        }
        return false;                
    }
}
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

时间复杂度：O(N2)
多过了10个点
这次没有创建任何对象，创建对象的开销大大减少。

class Solution {
    public boolean validPalindrome(String s) {
        int low = 0, 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) {
            char c1 = s.charAt(i), c2 = s.charAt(j);
            if (c1 != c2) {
                return false;
            }
        }
        return true;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/RQku0D/solution/zui-duo-shan-chu-yi-ge-zi-fu-de-dao-hui-30b55/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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

时间复杂度：0（N）

四、总结

• 学到了字符串处理的常见手段。
• 了解了String创建对象的开销
• 自己调优的尝试
• 遍历字符串的几种方式：charAt tocharArray 双指针