首页 > 代码库 > leetcode - Valid Palindrome

leetcode - Valid Palindrome

2024-07-21 12:13:27   219人阅读

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，构造一个新的字符串s1，它只包含原串的字母和数字，且字母都转成小写

2，再构造一个字符串s2，它是s1的反转字符串

3，判断s1和s2是否相等，若相等表明是回文串，否则不是

代码：

 1 #include <string> 2 //#include <cctype> 3 //#include <iostream> 4  5 using namespace std; 6  7 class Solution { 8 public: 9     bool isPalindrome(string s) {10         if (s.empty())11         {12             return true;13         }14 15         string s1("");16 17         for (int i = 0; i < s.length(); ++i)18         {19             if (s[i] <= ‘9‘ && s[i] >= ‘0‘) //数字20             {21                 s1.insert(s1.end(), s[i]);22             }23             else if (s[i] <= ‘Z‘ && s[i] >= ‘A‘) //大写字母24             {25                 s1.insert(s1.end(), tolower(s[i]));26             }27             else if (s[i] <= ‘z‘ && s[i] >= ‘a‘) //小写字母28             {29                 s1.insert(s1.end(), s[i]);30             }31         }32 33         string s2("");34 35         for (int i = s1.length() - 1; i >= 0; --i)36         {37             s2.insert(s2.end(), s1[i]);38         }39 40         if (!s1.compare(s2))41         {42             return true;43         }44         else45         {46             return false;47         }48     }49 };50 /*51 int main()52 {53     string s("A man, a plan, a canal: Panama");54 55     Solution so;56     cout << so.isPalindrome(s) << endl;57 58     system("pause");59 60     return 0;61 }62 */
View Code

 

这个思路简单、直接，但不是特别好，时间消耗O(n)，空间消耗O(n)，其实可以省去空间消耗，思路如下：

1，先将原串中的字母转成小写

2，然后设置两个指针，一个指向头，一个指向尾，若头尾指针都指向的数字或者字母（当某个指针指向其它字符，则跳过该字符，指向下一个字符，直到指向的是数字或者字母），就进行比较，相同则两个指针同时往中间走一步，直到头尾指针相遇，此时说明该串为回文串，若在比较过程中出现一次不同，则说明该串不是回文串

代码：

 1 #include <string> 2  3 using namespace std; 4  5 class Solution { 6 public: 7     bool isPalindrome(string s) { 8         if (s.empty()) 9         {10             return true;11         }12 13         for (string::iterator it = s.begin(); it != s.end(); ++it)14         {15             *it = tolower(*it);16         }17 18         string::iterator head = s.begin(), tail = prev(s.end());19 20         while(head < tail)21         {22             if (!isalnum(*head))23             {24                 ++head;25             }26             else if (!isalnum(*tail))27             {28                 --tail;29             }30             else if(*head != *tail)31             {32                 return false;33             }34             else35             {36                 ++head;37                 --tail;38             }39 40         }41 42         return true;43     }44 };
View Code

 

leetcode - Valid Palindrome


联系
我们