题解 | #判断是否为回文字符串#

题目的主要信息：

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

举一反三：

学习完本题的思路你可以解决如下题目：

BM13. 判断一个链表是否为回文结构

BM87. 合并两个有序数组

BM91. 反转字符串

方法一：首尾依次比较法（推荐使用）

知识点：双指针

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

思路：

回文字符串正向遍历与逆向遍历结果都是一样的，因此我们可以准备两个对撞指针，一个正向遍历，一个逆向遍历。

//首指针
int left = 0; 
//尾指针
int right = str.length() - 1;
//首尾往中间靠  
while(left < right){  
    ......
}

具体做法：

• step 1：准备两个指针，一个在字符串首，一个在字符串尾。
• step 2：在首的指针往后走，在尾的指针往前走，依次比较路过的两个字符是否相等，若是不相等则直接就不是回文。
• step 3：直到两指针在中间相遇，都还一致就是回文。因为首指针到了后半部分，走过的正好是尾指针走过的路，二者只是交换了位置，比较相等还是一样的。

图示：

Java代码实现:

import java.util.*;
public class Solution {
    public boolean judge (String str) {
        //首指针
        int left = 0; 
        //尾指针
        int right = str.length() - 1;
        //首尾往中间靠  
        while(left < right){  
            //比较前后是否相同
            if(str.charAt(left) != str.charAt(right)) 
                return false;
            left++;
            right--;
        }
        return true;
    }
}

C++代码实现:

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;
    }
};

Python实现代码：

class Solution:
    def judge(self , str: str) -> bool:
        #首指针
        left = 0 
        #尾指针
        right = len(str) - 1 
        #首尾往中间靠
        while left < right :
            #比较前后是否相同
            if str[left] != str[right] :
                return False
            left += 1
            right -= 1
        return True

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为字符串长度，最多遍历半个字符串
• 空间复杂度：$O(1)O(1)$，除了常数个临时变量，无额外辅助空间

方法二：反转字符串比较法（扩展思路）

思路：

既然字符串正向遍历与逆向遍历遇到字符都相等，那我们就反转字符串，看看它到底是不是正逆都一样，因为字符串支持整体比较，因此我们可以比较反转后的字符串与原串是不是相等。

具体做法：

• step 1：使用reverse函数将字符串反转。
• step 2：比较反转后的字符串，还是与原来的字符串相等，则是回文字符串。

Java代码实现:

import java.util.*;
public class Solution {
    public boolean judge (String str) {
        StringBuffer temp = new StringBuffer(str);
        //反转字符串
        String s = temp.reverse().toString();
        //比较字符串是否相等
        if(s.equals(str))
            return true;
        return false;
    }
}

C++代码实现:

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

Python实现代码：

class Solution:
    def judge(self , str: str) -> bool:
        temp = str
        #反转字符串
        str = str[::-1] 
        #比较字符串是否相等
        if temp == str:
            return True
        return False

复杂度分析：

• 时间复杂度：$O(n)O(n)$，反转字符串和比较字符串都是$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$，辅助字符串temp记录原来的字符串