Day62 验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写

https://leetcode-cn.com/problems/valid-palindrome/

将空字符串定义为有效的回文串

示例1：

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

示例2：

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

Java解法

思路：

• 这个属于很基础的题，使用双指针左右同时遍历即可，注意中间分段间隔，我就是漏掉了 Y到a的中间值导致提交出错一次

  
  image image

package sj.shimmer.algorithm.m3_2021;

/**
 * Created by SJ on 2021/3/30.
 */

class D62 {
    public static void main(String[] args) {
        System.out.println(isPalindrome("A man, a plan, a canal: Panama"));
        System.out.println(isPalindrome("race a car"));
        System.out.println(isPalindrome("ab_a"));
    }

    public static boolean isPalindrome(String s) {
        if (s == null) {
            return false;
        }
        int left = 0;
        int right = s.length() - 1;
        int interval = 'a' - 'A';
        while (left < right) {
            char cL = s.charAt(left);
            char cR = s.charAt(right);
            if (cL<'0'||cL>'y'||(cL>'9'&&cL<'A')||(cL>'Y'&&cL<'a')) {
                left++;
            } else if (cR<'0'||cR>'y'||(cR>'9'&&cR<'A')||(cR>'Y'&&cR<'a')) {
                right--;
            } else {
                if (cL == cR || (cL >= 'A' && (cL - interval == cR || cL + interval == cR))) {
                    left++;
                    right--;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

image

官方解

https://leetcode-cn.com/problems/valid-palindrome/solution/yan-zheng-hui-wen-chuan-by-leetcode-solution/

1. 筛选 + 判断

   双指针，类似我的处理

   字符翻转：s 翻转得到 s1 ，再翻转得到 s2，直接比较相等（中间可以过滤非字符非数字）

   • 时间复杂度：O(∣s∣)
   • 空间复杂度：O(∣s∣)

2. 在原字符串上直接判断

   双指针的优化：在移动指针时，不停移动，直到可以进行比较

   优化空间复杂度为O(1）