题目描述

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

  1. 输入: s = "A man, a plan, a canal: Panama"
  2. 输出: true
  3. 解释："amanaplanacanalpanama" 是回文串
  1. 输入: s = "race a car"
  2. 输出: false
  3. 解释："raceacar" 不是回文串

解题思路

双指针，前后匹配而已，确实是难度简单
一是先转小写之后用正则的方式替换掉不需要考虑的字符，然后前后匹配
优化的话就双指针while循环中直接忽略掉不需要考虑字符

实现代码

  1. class IsPalindrome {
  2.     // 预处理后再双指针
  3.     public boolean isPalindrome(String s) {
  4.         //先变小写，再正则替换
  5.         s = s.toLowerCase().replaceAll("[^a-z0-9]", "");
  6.         int n = s.length()/2;
  7.         for (int i = 0; i < n; i++) {
  8.             if (s.charAt(i) != s.charAt(s.length()-1-i)) {
  9.                 return false;
  10.             }
  11.         }
  12.         return true;
  13.     }
  14.     // 双指针优化
  15.     public boolean doublePointIsPalindrome(String s) {
  16.         int i = 0, j = s.length()-1;
  17.         s = s.toLowerCase();
  18.         while(i<j) {
  19.             while (!Character.isLetterOrDigit(s.charAt(i))&&i<j) {
  20.                 i++;
  21.             }
  22.             while (!Character.isLetterOrDigit(s.charAt(j))&&i<j) {
  23.                 j--;
  24.             }
  25.             if(s.charAt(i++)!=s.charAt(j--)){
  26.                 return false;
  27.             }
  28.         }
  29.         return true;
  30.     }
  31. }

时间及空间复杂度分析

时间复杂度O(N)
用正则进行预处理虽然简洁，但是时间耗时多了
image.png
不用正则的话，直接双指针忽略就快多了，2-3msimage.png
空间复杂度O(1)

拓展思路

看到一个用递归计算的，好像也行得通，妙啊👍