https://leetcode.com/problems/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.

 

• 字符串题。两种解法，一种是直接把string翻转比较，另一种是传统的首尾两个指针移动比较。
• 注意对指针-- end，end不能为size_t类型, 否则一旦被减为-1则会被转变为INT_MAX，程序进入死循环。
• 学习了string相关STL算法和函数，往string里添加char用push_back。
• toupper - C++ Reference
  • 　　http://www.cplusplus.com/reference/cctype/toupper/
• isalnum - C++ Reference
  • 　　http://www.cplusplus.com/reference/cctype/isalnum/?kw=isalnum
• transform - C++ Reference
  • 　　http://www.cplusplus.com/reference/algorithm/transform/?kw=transform
• string::push_back - C++ Reference
  • 　　http://www.cplusplus.com/reference/string/string/push_back/
• reverse_copy - C++ Reference
  • 　　http://www.cplusplus.com/reference/algorithm/reverse_copy/
• reverse_copy
  • 　　https://msdn.microsoft.com/zh-cn/library/c7ty5c36.aspx

1 #include 
      
        2 #include 
       
         3 #include 
        
           // toupper, isalnum 4 #include 
         
            // transform 5 using namespace std; 6  7 class Solution { 8 public: 9     bool isPalindrome(string s) 10     {11          string sTemp = "", sReverse = "";12 13          // Convert characters to UPPER14          transform(s.begin(), s.end(), s.begin(), ::toupper);15 16          // considering only alphanumeric characters17          for (int i = 0; i < s.length(); i ++)18              if (isalnum(s.at(i)))19                 sTemp.push_back(s.at(i)); // Appends character to the end of the string, increasing its length by one.20 21          // Need to allocate space if use reverse_copy22          sReverse.resize(sTemp.length());23          reverse_copy(sTemp.begin(), sTemp.end(), sReverse.begin());24 /*25          sReverse = sTemp;26          reverse(sReverse.begin(), sReverse.end());27 */         28 /*29          cout << sTemp << endl;30          cout << sReverse << endl;31 */         32          return sTemp == sReverse;33     }34     35     bool isPalindrome2(string s) 36     {37          int start = 0, end = s.length() - 1;38 39          while (start < end)40          {41                if ( !isalnum(s.at(start)) ) 42                   start ++;43                else if ( !isalnum(s.at(end)) ) 44                     end --;45                else if (toupper(s.at(start)) != toupper(s.at(end))) // Remember toupper 46                       return false;47                else48                {49                    // Remember to move ptr50                    start ++;51                    end --;52                }53          }54          55          return true;56     }57     58 };59 60 int main ()61 {62     Solution testSolution;63     string sTest[] = {
    "A man, a plan, a canal: Panama", "race a car"};64     65     for (int i = 0; i < 2; i ++)66         cout << testSolution.isPalindrome(sTest[i]) << endl;67     68     getchar();69     70     return 0;71 }