125. Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,"A man, a plan, a canal: Panama" is a palindrome."race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
题目大意：
回文的检测。
思路：
1.清洗字符串，得到只有数字和字母的字符串。
2.通过比较首尾的字符来判断。
代码如下：
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
class
Solution {
public
:
vector<string> stringSplit(string s,
const
char
* split)
{
vector<string> result;
const
int
sLen = s.length();
char
*cs =
new
char
[sLen + 1];
strcpy
(cs, s.data());
char
*p;
p =
strtok
(cs, split);
while
(p)
{
printf
(
"%s\n"
, p);
string tmp(p);
result.push_back(tmp);
p =
strtok
(NULL, split);
}
return
result;
}
bool
isPalindrome(string s) {
if
(s.size() == 0 || s.size() == 1)
return
true
;
vector<string> vecStrs = stringSplit(s,
" ~!@#$%^&*().,:;-?\"'`"
);
s =
""
;
for
(
int
i = 0; i < vecStrs.size(); i++)
s += vecStrs[i];
if
(s.size() == 1 || s.size() == 0)
return
true
;
int
i = 0;
for
(; i < s.size() / 2; i++)
{
if
(s[i] <= 57 || s[s.size() - i - 1] <= 57)
{
if
(s[i] == s[s.size() - i - 1])
{
continue
;
}
else
{
return
false
;
}
}
else
if
(s[i] == s[s.size() - i - 1] ||
s[i] - s[s.size() - i - 1] == 32 ||
s[s.size() - i - 1] - s[i] == 32)
{
continue
;
}
else
{
return
false
;
}
}
return
true
;
}
};
|
上面的做法效率低下，还有对API不熟悉。
下面是对上面的改进：
参考https://discuss.leetcode.com/topic/48376/12ms-c-clean-solution
代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class
Solution {
public
:
bool
isPalindrome(string s) {
int
i = 0, j = s.size() - 1;
while
(i < j)
{
while
(!
isalnum
(s[i]) && i < j) i++;
while
(!
isalnum
(s[j]) && i < j) j--;
if
(
tolower
(s[i++]) !=
tolower
(s[j--]))
return
false
;
}
return
true
;
}
};
|
这里使用了isalnum()函数来判断是否为文字数字。
通过使用tolower()来统一字符的大小写，都变为小写。
本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1836839
