LeetCode算法题-Valid Palindrome II（Java实现）

佚名 5年前 (2019-03-25) 算法 1567人围观抢沙发百度已收录

这是悦乐书的第287次更新，第304篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第155题（顺位题号是680）。给定非空字符串s，最多可以删除一个字符。判断它是否是回文。例如：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入：“aba”
输出：true

输入：“abca”
输出：true
说明：可以删除字符“c”让其变为回文。

注意：该字符串仅包含小写字符a-z。字符串的最大长度为50000。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

暴力解法。首先，如果字符串长度在2以内，直接返回true。然后利用StringBuilder类，借助其reverse方法，判断是否为回文。如果上面两种情况都不满足，就使用循环，每次对原字符串进行截取，来实现删掉一位的效果，组成新的字符串来判断是否为回文。但是此解法会超时。

public boolean validPalindrome(String s) {
    if (s.length() <= 2) {
        return true;
    }
    StringBuilder sb = new StringBuilder(s);
    String ss = sb.reverse().toString();
    if (s.equals(ss)) {
        return true;
    }
    for (int i=0; i<s.length(); i++) {
        if (i == 0) {
            if (isPalindrome(s.substring(1, s.length()))) {
                return true;
            }
        } else if (i < s.length()-1) {
            if (isPalindrome(s.substring(0, i)+ s.substring(i+1, s.length()))) {
                return true;
            }
        } else if (i == s.length()-1) {
            if (isPalindrome(s.substring(0, s.length()-1))) {
                return true;
            }
        }
    }
    return false;
}

public boolean isPalindrome(String ss){
    StringBuilder sb = new StringBuilder(ss);
    String sss = sb.reverse().toString();
    if (ss.equals(sss)) {
        return true;
    }
    return false;
}

03 第二种解法

第一种解法会超时，因为考虑了所有可能存在的多余的那个字符，但是我们真的需要考虑那么多吗？因为题目说了，只有一次删除字符的机会，那么我们在处理的时候，只处理一种情况就好，不符合就直接返回false。

依旧使用截取字符串的方式，如果遇到左右字符不对称的情况，就表示遇到了多余的字符，此时需要考虑是删掉左边的还是右边的？只要两个中符合一个就可以返回true，所以用或连接。将左右两字符不等的索引范围内的字符串进行截取，一个后面少截取一位，一个前面少截取一位，判断截取的字符串是否为回文。

public boolean validPalindrome(String s) {
    if (s.length() <= 2) {
        return true;
    }
    StringBuilder sb = new StringBuilder(s);
    String ss = sb.reverse().toString();
    if (s.equals(ss)) {
        return true;
    }
    for (int i=0; i<s.length()/2; i++) {
        if (s.charAt(i) != s.charAt(s.length()-1-i)) {
            return isPalindrome(s.substring(i, s.length()-1-i)) || isPalindrome(s.substring(i+1, s.length()-i));
        }
    }
    return true;
}

public boolean isPalindrome(String ss){
    StringBuilder sb = new StringBuilder(ss);
    String sss = sb.reverse().toString();
    if (ss.equals(sss)) {
        return true;
    }
    return false;
}

04 第三种解法

思路与第二种解法相似，但是比较轻便，借助双指针来实现。一左一右取字符比较，如果不等，表示遇到了需要删除的字符，同样分两种情况，删右边的一位和删左边的一位，再去判断这中间的子字符串是否为回文即可。

public boolean validPalindrome(String s) {
    // 使用双指针
    int left = 0;
    int right = s.length()-1;
    while (left < right) {
        // 如果左右指针所在的字符不相等，那就删掉右边的或者删掉左边的字符，再判断
        if (s.charAt(left) != s.charAt(right)) {
            return isPalindrome(s, left, right-1) || isPalindrome(s, left+1, right);
        }
        left++;
        right--;
    }
    return true;
}

// 辅助方法，判断一个字符串在（left,right）内是否为回文
public boolean isPalindrome(String s, int left, int right){
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}