【leetcode】Valid Palindrome
Question：
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.
Anwser 1：
class Solution {
public:
bool isStr(char &ch){
if(ch >= '0' && ch <= '9'){
return true;
} else if(ch >= 'a' && ch <= 'z'){
return true;
} else if(ch >= 'A' && ch <= 'Z'){
ch += 32;
return true;
}
return false;
}
bool isPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int len = s.length();
if(len == 0){
return true;
}
string str = "";
for(int i = 0; i < len; i++){ // remove illegal char, such as "?" "/" ...
if(isStr(s[i])){
str += s[i];
}
}
len = str.length();
int mid = (len + 1) / 2;
for(int i = 0; i < mid; i++){
if(str[i] != str[len - 1 - i]){ // check front and end char
return false;
}
}
return true;
}
};Anwser 2：
class Solution {
public:
bool isStr(char &ch){
if(ch >= '0' && ch <= '9'){
return true;
} else if(ch >= 'a' && ch <= 'z'){
return true;
} else if(ch >= 'A' && ch <= 'Z'){
ch += 32;
return true;
}
return false;
}
bool isPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int len = s.length();
if(len == 0){
return true;
}
int i = 0;
int j = len - 1;
while(i < j){
if(!isStr(s[i])) {
i++;
} else if(!isStr(s[j])) {
j--;
} else if(s[i++] != s[j--]) {
return false;
}
}
return true;
}
};注意点：
1） 字母数字判断，注意字母中的字母大小写转换（把大写加32全部转化成小写）
2） 方法2中采用判断删除的方法，效率要高，且不占用另外字符串存储（str）
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2013年04月14日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读