题海拾贝：LCR018.验证回文串

           Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！

我的博客：<但凡.

我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》

欢迎点赞，关注！

1、题目

2、

2、题解 

        这个题如果没有空格和符号的话，那就直接双指针了，或者拿个C++里面的reverse反转一下。但问题是它有空格和各种符号，那就得考虑考虑了。

        第一种思路，我们先把所有的符号去掉，存到一个新的字符串里，然后对那个字符串进行判断。双指针啊迭代器啊，甚至你拿C风格的字符数组做都行。

        第二种思路，我们检测到空格和符号时就跳过，然后我们在继续判断。

第一种（c++实现）：

class Solution {
public:
    bool isPalindrome(string s) {
    int i = 0;
    string h;
    for (char ch : s)
    {
        if (isalnum(ch))
        {
            h.push_back(tolower(ch));
        }
    }
    string::iterator it1 = h.begin();
    string::iterator it2 = h.end();
    it2--;
    while (it2 - it1 >= 0)
    {
        
        if (*it1 != *it2)
        {
            return false;
        }
        it1++;
        it2--;
    }
    return true;
}
};

 第二种（c++实现）：

#include<algorithm>
class Solution {
public:
    bool isPalindrome(string s) {
  
        string h;
        for(char ch:s)
        {
            if(isalnum(ch))
            {
                h.push_back(tolower(ch));
            }
        }
       int i=0;
       int j=h.size();
       if(i==j)
       {
        return true;
       }
        while(j-i>=0)
        {
            if(h[i]!=h[j-1])
            {
                return false;
            }
            i++;
            j--; 
        }
        return true;
    }
};

        以上这两种都是第一种思路。但是千万别忘了转换成小写字母。

        但是既然都用c++了，以上两种方法就有点鸡肋了，不如直接reverse。

第三种（c++reverse）：

class Solution {
    #include<algorithm>
public:
   bool isPalindrome(string s) {
    int i = 0;
    string h;
    for (char ch : s)
    {
        if (isalnum(ch))
        {
            h.push_back(tolower(ch));
        }
    }
    string v = h;//记录反转之前的
    reverse(h.begin(), h.end());
    if (h==v)
        return true;
    else
        return false;
}
};

第四种（思路二）：

        这种方法略优一些。

class Solution {
public:
    bool isPalindrome(string s) {
     int i = 0;
     string::iterator it1 = s.begin();
     string::iterator it2 = s.end();//指向字符串最后一个字符的下一个位置
     it2--;//让it2指向最后一个字母
     while (it2 - it1 >= 0)
     {
         while (isalnum(*it1) == 0&&it1!=it2)//&&后面的一定要有，不然连着三个空格直接栈溢出你就老实了。
         {
             it1++;
         }
         while (isalnum(*it2) == 0&&it1!=it2)
         {
             it2--;
         }
         *it1=tolower(*it1);//这个函数有返回值得接受，不然就是没改
         *it2=tolower(*it2);
         if (*it1 != *it2)
         {
             return false;
         }
        
         it1++;
         it2--;
     }
     return true;
 }
};

        好了，今天的内容就分享到这，我们下期再见！