680. Valid Palindrome II

本文主要是介绍680. Valid Palindrome II，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这道题的暴力解法很简单，先check如果不删除任何字符，是否字符串是回文，如果不是，再挨个删除每个字符，check删除字符之后是否是回文。

时间复杂度O(n2), n是字符串s的长度，字符串很长的情况下会TLE，算法如下：

class Solution {
    public boolean validPalindrome(String s) {
        if(checkPalindrom(s))
            return true;
        for(int i=0;i<s.length();i++){
            if(checkPalindrom(s.substring(0, i)+s.substring(i+1)))
                return true;
        }
        return false;
        
    }
    
    private boolean checkPalindrom(String s){
        int i=0, j=s.length()-1;
        while(i<j){
            if(s.charAt(i)==s.charAt(j)){
                i++;
                j--;
            }
            else
                return false;
        }
        return true;
    }
}

上面的算法，每删掉一个字符，就要从头到尾重新挨个字符check一遍字符串，其实这个过程可以one pass，而且这个算法可以延伸到去掉任意数量的字符.

时间复杂度O(n), 算法如下：

class Solution {
    public boolean validPalindrome(String s) {
        return helper(s, 0, s.length()-1, 0);
    }
    
    private boolean helper(String s, int i, int j, int sum){
        if(sum>1)
            return false;
        while(i<j && s.charAt(i)==s.charAt(j)){
            i++;
            j--;
        }
        if(i>=j)
            return true;
        return helper(s, i+1, j, sum+1) || helper(s, i, j-1, sum+1);
    }
}

这篇关于680. Valid Palindrome II的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！