题解 | NC141判断回文

判断回文

描述
给定一个字符串，请编写一个函数判断该字符串是否回文。如果回文请返回true，否则返回false。

回文串定义为一个正读和反读都一样的字符串，例如“aooa”,“a”等。
易知长度为0的字符串必定不为回文串，长度为1的字符串必定为回文串。
当字符串长度大于1时，可以有以下几种解法：

解法1: 判断 是否成立
进行次判断，如果出现一次 ，该字符串就不是回文串，如果所有判断全都相等，那么该字符串是回文串。时间复杂度：，空间复杂度：。

核心代码：

class Solution {
public:
    bool judge(string str) {
        // write code here
        int n=str.length(); //获取字符串长度
        if(n==0){
            return false;
        }
        else if(n==1){
            return true;
        }
        for(int i=0;i<n/2;i++){ //使用for循环进行逐一比较
            if(str[i]!=str[n-i-1]){
                return false;
            }
        }
        return true;
    }
};

解法2: 双指针法
使用两个指针分别指向字符串两端的字符，指针分别向后及向前移动，移动同时比较两个指针所指向的值是否相同，若不相同时则表示此字符串不是回文串；若两指针相遇时未出现不相同的字符，那么该字符串就是回文串。时间复杂度：，空间复杂度：。

举个例子，对于“abba”这个字符串进行判断的时候，指针的判断顺序是这样的：

另一个例子是“abca”:

核心代码：

class Solution {
public:
    bool judge(string str) {
        // write code here
        int n=str.length();
        if(n==0){
            return false;
        }
        else if(n==1){
            return true;
        }
        int left=0; //定义左端指针
        int right=n-1; //右端指针
        while(left<right&&left!=right){
            //使用指针逐一向后及向前扫
            if(str[left]==str[right]){ 
                left+=1;
                right-=1;
            }
            else{
                //如遇到指针所指向的字符不相等，那么该字符串就不是回文串
                return false;
            }
        }
        //所有比较结束，为找到不相同字符，该字符串为回文串
        return true;
    }
};