iven 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.
拿这个练习了下stack。注意top和pop。pop是不返回元素的。
|
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 |
class
Solution {public: bool
isPalindrome(string s) { int
l = s.length(); stack<char> st; for(int
i = 0 ; i < l ; i++) { if(s[i] >= ‘a‘
&& s[i] <= ‘z‘|| s[i] >=‘0‘&&s[i]<=‘9‘)st.push(s[i]); else
if(s[i] >= ‘A‘
&& s[i] <= ‘Z‘) st.push(s[i]-‘A‘+‘a‘); } for(int
i = 0 ; i < l ; i++) { if(s[i] >= ‘a‘
&& s[i] <= ‘z‘
|| s[i] >=‘0‘&&s[i]<=‘9‘) { char
temp = st.top(); st.pop(); if(temp != s[i]) return
0; } else
if(s[i] >= ‘A‘
&& s[i] <= ‘Z‘) { char
temp = st.top() -‘a‘+‘A‘; st.pop(); if(temp != s[i]) return
0; } } return
1; }}; |
这个题有更优的解法，也不用栈。
左右两个指针，分别指到第一个合法字符之后开始判断，之后一个向左一个向右，如此反复指到两个指针相遇。
Valid Palindromed,布布扣,bubuko.com
原文：http://www.cnblogs.com/pengyu2003/p/3580450.html