【Java面试手册-算法篇】给定一个字符串，请判断是否为回文字符串？

回文字符串的定义：

回文字符串是指一个字符串从左到右与从右到左遍历得到的序列是相同的。也就是说不管从左读，还是从右读，都是一样的，类似数学上学习的轴对称图形，例如“abcba”、“NBAABN”是回文字符串，而“abcd”不是回文字符串。

常见的实现思路有以下两种：

• 首尾双向遍历，如果某个字符不相同，则不是回文字符串；
• 反转字符串，比较反转后的字符串与原字符串是否相同；

示例1 — 首尾双向遍历

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

        int low = 0;
        int high = str.length() - 1;
        while (low < high) {
            if (str.charAt(low) != str.charAt(high)) {
                return false;
            }
            low++;
            high--;
        }

        return true;
    }

也可以采用for循环来实现首尾双向遍历，如下：

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

        int length = str.length();
        for (int low = 0, high = length - 1; low < high; low++, high--) {
            if (str.charAt(low) != str.charAt(high)) {
                return false;
            }
        }

        return true;
    }

示例2 — 反转字符串

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

        char[] chars = str.toCharArray();
        for (int start = 0, end = chars.length - 1; start <= end; start++, end--) {
            char tempChar = chars[start];
            chars[start] = chars[end];
            chars[end] = tempChar;
        }

        return String.valueOf(chars).equals(str);
    }

上面反转字符串也是采用了首尾双向遍历的思路，通过临时变量的方式，实现两个字符的交换。除了首尾双向遍历方式外，也可以采用单向遍历的方式实现字符串的反转，如下：

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

        int length = str.length();
        char[] chars = new char[length];
        for (int i = 0; i < length; i++) {
            chars[i] = str.charAt(length - i - 1);
        }

        return String.valueOf(chars).equals(str);
    }

上面的两种方式，都是采用直接遍历的方式，当然也可以借助 StringBuilder 或 StringBuffer 的 reverse() 方法实现字符串反转，然后再判断字符串是否为回文字符串

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

        return new StringBuilder(str).reverse().toString().equals(str);
    }

或

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

        return new StringBuffer(str).reverse().toString().equals(str);
    }

延伸：

• 给定一个字符串，如何实现字符串的反转？
• 给定一个数组，如何实现数组元素的反转？

测试验证

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

输出的结果如下：

false
true
false
true

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