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);
    }
}

 

上一篇:微信小程序开发教程目录


下一篇:Spring运行报警告Cannot find template location: classpath:/templates/ (please add some templates or check