125.验证回文串Java

题目描述

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

说明：本题中，我们将空字符串定义为有效的回文串。

输入输出样式

示例1：
输入: “A man, a plan, a canal: Panama”
输出: true

示例2：
输入: “race a car”
输出: false

本题来自LeetCode：https://leetcode-cn.com/problems/valid-palindrome/

思路

用双指针头尾往中间扫描，边扫描边作比较。需要注意的是：1. 大小写被认为是同一字符； 2. 如果当前扫描的不是字母或数字，那么指针应该移动，直到指向字母或数字

算法分析

时间复杂度O(s.length()），空间复杂度为O(1)

求解函数

public boolean isPalindrome(String s) {
        if (s.length() == 0) return true;
        int left = 0, right = s.length() - 1;
        while(true) {
        	//当前扫描不是字母或数字，且指针未越界就移动，直到所指是字母或数字
            while (judgeChar(s.charAt(left))== -1 && left < s.length() - 1) ++left;
            while (judgeChar(s.charAt(right)) == -1 && right > 0) --right;
            if (left < right) {
            	//双指针所指的字符不同
                if (s.charAt(left) != s.charAt(right)) {
                	//如果是同一字母的大小写(相差32)，也认为是同一字符
                    if (judgeChar(s.charAt(left)) == judgeChar(s.charAt(right)) && Math.abs(s.charAt(left) - s.charAt(right)) == 32) {
                        ++left;
                        --right;
                        continue;
                    }
                    return false;
                }
                ++left;
                --right;
            } else return true;
        }
    }

	// 判断字符是大写还是小写字母或数字
    public int judgeChar(char ch) {
        if (ch >= 'a' && ch <='z' || ch >='A' &&ch <= 'Z') {
            return 1;
        }
        if (ch >='0' && ch <= '9') {
            return 2;
        }
        return -1;
    }