LeetCode中验证回文串题解-java
题目
125. 验证回文串
难度简单300
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
题解
方法一:双指针
思路
使用i和j两个头尾指针,来遍历这个字符串,当遇到不是字母和数字时,跳过这个字符,前往下一个字符,若两者为数字或者字母时,判断两者是否相等(字母大小写忽略),若相等,i与j均往下走一步,若不相等,返回false,此结束条件为一直到i与j重合,即i=j,结束循环,
代码实现
class Solution {
public boolean isPalindrome(String s) {
if(s == null){
return true;
}
int j = s.length() - 1;
int i = 0;
while( i < j){
if(!Character.isLetterOrDigit(s.charAt(i))){
i++;
continue;
}else if(!Character.isLetterOrDigit(s.charAt(j))){
j--;
continue;
}
if(Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))){
return false;
}else{
i++;
j--;
}
}
return true;
}
}
复杂度分析
- 时间复杂度:O(N),其中 N 是字符串 s 的长度。
- 空间复杂度:O(1)。