125.验证回文串Java

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;
    }
上一篇:牛客-NC1-大数加法


下一篇:leetcode-227-基本计算器||