125. 验证回文串

た入场券 2022-12-07 12:03 190阅读 0赞

# 题目： #

[125. 验证回文串][125.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解： #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][2020091516551810.png_pic_center]

## 1. 题解一：正则表达式 ##

我们还可以使用正则匹配，把特殊字符过滤掉，只留下字母和数字，然后转化为小写，再反转，最后在判断是否相等。当然这种写法只是提供了一种思路，面试中如果写出这种肯定还会让你再写一种的，因为它没有完全考察出对这题的解题思路。

## 2. 题解二：双指针中的左右指针 ##

最简单的就是使用双指针，一个指向前，一个指向后，遇到空格以及特殊字符要跳过，然后判断。  
![在这里插入图片描述][20200915165314750.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]

# 代码： #

## 1. 代码一：正则表达式 ##

// 方法1: 正则表达式
    public static boolean isPalindrome(String s) { 
        String actual = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
        String rev = new StringBuilder(actual).reverse().toString();
        return actual.equals(rev);
    }

## 2. 代码二：双指针中的左右指针 ##

public class code125 { 
    
        // 方法2: 双指针中的左右指针
        public static boolean isPalindrome(String s) { 
            if(s.isEmpty())
            { 
                return true;
            }
            // 从头到尾一一比较即可，遇到除字母和数字字符的字符跳过
            int left = 0;
            int 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(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))
                { 
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }
    
        public static void main(String[] args) { 
            String s1 = "A man, a plan, a canal: Panama";
            boolean res1 = isPalindrome(s1);
            System.out.println(res1);
    
            String s2 = "race a car";
            boolean res2 = isPalindrome(s2);
            System.out.println(res2);
        }
    }

# 参考： #

1.  [验证回文串][Link 1]
2.  [java的4种解题方式][java_4]
3.  [\[Java\] 大道至简 6行][Java_ _ 6]
4.  [JAVA双指针][JAVA]
5.  [验证回文串（双指针法）][Link 2]
6.  [正则或者双指针][Link 3]

[125.]: https://leetcode-cn.com/problems/valid-palindrome/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/82cf5d834e924b42a15b0d6fa3a23bf3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/09e63c76d48f41b189706697784344c8.png
[2020091516551810.png_pic_center]: /images/20221123/f7eca88ab8de4832b672fc216da4c3af.png
[20200915165314750.png_pic_center]: /images/20221123/d3c6e22477ee4149b215fda3072147c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/a11f0d88ba0e4c0c9e63472260b3be0d.png
[Link 1]: https://leetcode-cn.com/problems/valid-palindrome/solution/yan-zheng-hui-wen-chuan-by-leetcode-solution/
[java_4]: https://leetcode-cn.com/problems/valid-palindrome/solution/javade-4chong-jie-ti-fang-shi-by-sdwwld/
[Java_ _ 6]: https://leetcode-cn.com/problems/valid-palindrome/solution/java-da-dao-zhi-jian-6xing-by-rabbitzhao/
[JAVA]: https://leetcode-cn.com/problems/valid-palindrome/solution/javashuang-zhi-zhen-by-starlikemoon/
[Link 2]: https://leetcode-cn.com/problems/valid-palindrome/solution/valid-palindrome-shuang-zhi-zhen-fa-by-jyd/
[Link 3]: https://leetcode-cn.com/problems/valid-palindrome/solution/zheng-ze-huo-zhe-shuang-zhi-zhen-by-powcai/