leetCode125.ValidPalindrome字符串
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: vectorstringSplit(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
本文名称:leetCode125.ValidPalindrome字符串
本文网址:http://scyanting.com/article/jdogpg.html