125. Valid Palindrome
创新互联从2013年创立，先为海阳等服务建站，海阳等地企业，进行企业商务咨询服务。为海阳企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
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.通过比较首尾的字符来判断。
代码如下：
class Solution {
public:
vector stringSplit(string s, const char * split)
{
vector 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 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
代码如下：
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()来统一字符的大小写，都变为小写。
2016-08-11 13:26:25
