题解 | #判断回文#

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

方法一：暴力解法--直接反转字符串，判断是否相等

求解思路
对于本题目，判断是否是回文，我们用最直接的方法，将字符串直接翻转过来，然后判断是否相等即可。

图片说明

解题代码

import java.util.*;
public class Solution {
    public boolean judge (String str)
    {
    String hyres = new StringBuffer(str).reverse().toString(); // 反转字符串
    return str.equals(hyres); // 判断是否相等
    }
}

复杂度分析
时间复杂度：一层循环来翻转字符串，因此时间复杂度为 $O(N)$
空间复杂度：存储翻转后的字符串，引入了额外的内存地址空间，因此空间复杂度为 $O(N)$

方法二：优化方法--双指针的思想

求解思路
对第一种方法进行优化，采用双指针，一个指针从头到尾，另一个指针从尾到头。两个指针开始跑遍字符串，当两个指针碰头时，则为回文，否则不是回文。

图片说明

解题代码

import java.util.*;
public class Solution {
    public boolean judge (String str) {
        if (str.length() == 0)  return true;
        int left = 0; // 左指针
        int right = str.length() - 1; // 右指针
        while (left < right) // 两个指针，一个从左边开始，一个从右边开始，每次两个
        {
            if (str.charAt(left++) != str.charAt(right--))
                return false; // 指针都同时往中间跑，只要两个指针指向的字符不一样就返回false
        }
        return true;
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：没有引入新的内存地址空间，因此空间复杂度为 $O(1)$