题解 | #判断回文#

思路：

题目的主要信息：

• 判断字符串是否是回文字符
• 回文字符即首尾相互往中靠，字符都是相同的

方法一：首尾依次比较法
具体做法：
两个指针，一个在字符串首，一个在字符串尾，在首的指针往后走，在尾的指针往前走，依次比较路过的两个字符是否相等，直到两指针在中间相遇。（我们这里用下标代替指针）

class Solution {
public:
    bool judge(string str) {
        int left = 0; //首
        int right = str.length() - 1;  //尾
        while(left < right){  //首尾往中间靠
            if(str[left] != str[right]) //比较前后是否相同
                return false;
            left++;
            right--;
        }
        return true;
    }
};

复杂度分析：

• 时间复杂度：，最多遍历半个字符串
• 空间复杂度：，除了临时变量，无额外空间

方法二：反转字符串比较法
具体做法：
因为回文字符串首尾部分相同，所以可以将其用reverse函数反转，若是还是与原来的字符串相等，则是回文字符串。

class Solution {
public:
    bool judge(string str) {
        string temp = str;
        reverse(str.begin(), str.end()); //反转字符串
        if(temp == str)
            return true;
        return false;
    }
};

复杂度分析：

• 时间复杂度：，逆转和比较都是
• 空间复杂度：，辅助字符串temp记录原来的字符串