题目链接

剑指 Offer II 018. 有效的回文 easy

题目描述

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

本题中，将空字符串定义为有效的 回文串 。

示例 1:

输入: s = “A man, a plan, a canal: Panama”
输出: true
解释：“amanaplanacanalpanama” 是回文串

示例 2:

输入: s = “race a car”
输出: false
解释：“raceacar” 不是回文串

提示 :

• 1<=s.length<=2∗1051 <= s.length <= 2 * 10^51<=s.length<=2∗105
• 字符串 s由 ASCII字符组成

分析：

先把合法字符转成小写 加到 s中。

用两个指针判断是否是回文串即可。

时间复杂度：O(n)O(n)O(n)

C++代码：

class Solution {
public:bool isPalindrome(string ss) {string s;for(auto c:ss){if(isalnum(c)) s += tolower(c);}int n = s.size();for(int i = 0,j = n - 1;i < j;i++,j--){if(s[i] != s[j]) return false;}return true;}
};

Java代码：

class Solution {public boolean isPalindrome(String ss) {StringBuilder sb = new StringBuilder();for(var c:ss.toCharArray()){if(Character.isLetterOrDigit(c))  sb.append(Character.toLowerCase(c));}int n = sb.length();for(int i = 0,j = n - 1;i < j;i++,j--){if(sb.charAt(i) != sb.charAt(j)) return false;}return true;}
}