本文共 2100 字,大约阅读时间需要 7 分钟。
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
转载地址:http://rlcix.baihongyu.com/