LeetCode刷题_125.验证回文串

原题地址：125. 验证回文串

题目描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

输入: "race a car"
输出: false

解题思路

直观解题：清理+比较

1. 删除字符串中除字母和数字以外的字符
   - 方法一：使用API：s.replaceAll("[^A-Za-z0-9]", "");（**效率低**）
   - 方法二：将字符串转换成字符数组，循环遍历。涉及到的API：Character.isLetterOrDigit(ch)
2. 将字符串翻转并比较
   - 使用字符串API：new StringBuffer(s).reverse()

public static boolean isPalindrome(String s) {
	StringBuffer sgood = new StringBuffer();
    for(int i = 0; i < s.length(); i++){
    	char ch = s.charAt(i);
    	if(Character.isLetterOrDigit(ch)){
            sgood.append(Character.toLowerCase(ch));
        }
    }
    StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
    return sgood_rev.toString().equals(sgood.toString());
}

第二种比较方法：双指针

观察上面解法发现，我们创建了两个StringBuffer对象用来存放去除特殊字符后的字符串以及它的翻转字符串，其实我们可以不翻转，使用双指针在一个字符串上比较

• 初始时，左右指针分别在sgood的两端，随后不断的将两个指针相向移动，每次移动一步 ，并判断两个指针指向的字符是否相同，当两个指针相遇时，就说明sgood是回文串

public static boolean isPalindrome(String s){
   StringBuffer sgood = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch));
            }
        }
        int left = 0;
        int right = sgood.length()-1;
        while (left < right) {
            if (sgood.charAt(left) != sgood.charAt(right)) {
                return false;
            } else {
                left++;
                right--;
            }
        }
        return true;
}

方法二：在原字符串上直接判断

上面解法中

• 时间复杂度：O(|s|)，s是字符串的长度；
• 空间复杂度：O(|s|)，我们需要将字母和数字存放在新的字符串中，最坏情况参数字符串中没有特殊字符，新字符串sgood和原字符串s等长，因此我们需要O(|s|)的空间。

假如我们不创建新的字符串，所有操作都在原字符串上进行那么空间复杂度就可以实现O(1)。

在比较两端字符是否相等前先判断两个指针所指向的字符是否是特殊字符，如果是则继续移动一步，直到指针所指位置不是特殊字符为止

    public static boolean isPalindrome2(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            if (left < right) {
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false;
                }
                left++;
                right--;
            }
        }
        return true;
}

最终

时间复杂度：O(n)
空间复杂度：O(1)

LeetCode刷题_125.验证回文串

原文：https://www.cnblogs.com/daidai8/p/14782091.html