题目地址(125. 验证回文串)
https://leetcode-cn.com/problems/valid-palindrome/
题目描述
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串
示例 2:
输入: "race a car"
输出: false
解释："raceacar" 不是回文串
提示：
1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成
|
前置知识
公司
代码
Java
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class Solution {
public boolean isPalindrome(String s) {
if(s.equals(" ")) return true;
String str="";
for(int i=0;i<s.length();i++){
if(s.charAt(i)>47&&s.charAt(i)<58)
str=str+s.charAt(i);
if(s.charAt(i)>64&&s.charAt(i)<91)
str=str+s.charAt(i);
if(s.charAt(i)>96&&s.charAt(i)<123)
str=str+s.charAt(i);
}
str=str.toLowerCase();
if(str.equals("")) return true;
System.out.print(str);
int left=0;
int right=str.length()-1;
while(left<=right){
if(str.charAt(left)!=str.charAt(right))
return false;
else {
left++;
right--;
}
}
return true;
}
}
|
补充
此题还有两种思路：
+去掉空格，标点等之后，直接将字符串反转，将反转后的字符串与原字符串进行对比，得出结果（整体思路与双指针的类似 ）
- 直接使用双指针向内收缩，遇到标点等非法字符直接跳过，仅比较合法的字符。
复杂度分析
令 n 为数组长度。