【Java面试手册-算法篇】给定一个非空字符串，最多删除一个字符，判断是否能成为回文字符串

回文字符串是指一个字符串从左到右与从右到左遍历得到的序列是相同的。也就是说不管从左读，还是从右读，都是一样的。

比如 “abcba”、“aaa” 是回文字符串，而 “abca” 不是回文字符串，但是从 "abca" 中删除一个 b 或 c 得到的新字符串 "aca" 或 "aba" 就是回文字符串。

实现思路：

• 采用首尾双向循环（双指针）方式，当遇到字符不相同的时候，分为两种情况
  • 删除左侧的一个字符（相当于左指针向右移动一位），然后比较和右指针组成的子串是否为回文字符串即可；
  • 删除右侧的一个字符（相当于右指针向左移动一位），然后比较和左指针组成的子串是否为回文字符串即可；

示例代码1 — while循环：

private static boolean isPalindrome(String str) {
        if (str == null) {
            return false;
        }
        
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return isPalindrome(str, left + 1, right) || isPalindrome(str, left, right - 1);
            }
            left++;
            right--;
        }

        return true;
    }

    /**
     * 比较子串是否为回文字符串
     * @param str
     * @param left
     * @param right
     * @return
     */
    private static boolean isPalindrome(String str, int left, int right) {
        if (str == null) {
            return false;
        }
        
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }

        return true;
    }
           

因为最多只能删除一个字符，当遇到第一个不相同的字符时，再比较最多两次即可，上面的实现是采用while循环的方式，也可以采用for方式来实现。

示例代码2 — for循环

private static boolean isPalindrome(String str) {
        if (str == null) {
            return false;
        }

        char[] chars = str.toCharArray();
        for (int left = 0, right = chars.length - 1; left < right; left++, right--) {
            if (chars[left] != chars[right]) {
                return isPalindrome(chars, left + 1, right) || isPalindrome(chars, left, right - 1);
            }
        }

        return true;
    }

    private static boolean isPalindrome(char[] chars, int left, int right) {
        for (; left < right; left++, right--) {
            if (chars[left] != chars[right]) {
                return false;
            }
        }

        return true;
    }
           

测试验证

public static void main(String[] args) {
        System.out.println(isPalindrome("abcd"));
        System.out.println(isPalindrome("abca"));
        System.out.println(isPalindrome("abcba"));
        System.out.println(isPalindrome("abcda"));
    }
           

输出的结果如下：

false

true

true

false

更多有关Java面试相关的知识点可以关注【Java面试手册】小程序，涉及Java基础、多线程、JVM、Spring、Spring Boot、Spring Cloud、Mybatis、Redis、数据库、数据结构与算法等。