关于java: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、数据库、数据结构与算法等。