题解 | #判断回文#

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

输入：
"absba"
返回值：
true

方法一：双指针
设置两个指针 $start,end$ 分别位于字符串的开头和末尾， $start$ 向左移动， $end$ 向右移动，指针未相遇时，如果两指针所指向的值不相等直接返回 $false$ ，否则循环结束时返回 $true$ .

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param str string字符串 待判断的字符串
     * @return bool布尔型
     */
    public boolean judge (String str) {
        // write code here
        int start=0,end=str.length()-1;
        while(start<end)
        {
            //指针指向的字符不一样时就返回false
            if(str.charAt(start)!=str.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

复杂度：

时间复杂度：字符串长度为 $n$ ,平均时间复杂度为 $O(n)$
空间复杂度：未使用辅助空间， $O(1)$

方法二：调用reverse()函数

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param str string字符串 待判断的字符串
     * @return bool布尔型
     */
    public boolean judge (String str) {
        // write code here
        String str2=new StringBuffer(str).reverse().toString();
        return str.equals(str2);
    }
}

复杂度：

时间复杂度：reverse函数的平均时间复杂度为 $O(n)$
空间复杂度：辅助空间为 $n$ , $O(n)$

方法三：利用栈
先将字符串中的字符逐个进栈，利用栈先进后出的特点，将字符逐个出栈并与字符串中的字符从头到尾逐个比较，不相等直接返回 $false$ ,否则循环结束返回 $true$ .

图片说明

代码如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param str string字符串 待判断的字符串
     * @return bool布尔型
     */
    public boolean judge (String str) {
        // write code here
        Stack<Character>s=new Stack<>();
        int i;
        for(i=0;i<str.length();i++)
        {
            char c=str.charAt(i);
            s.push(c);

        }
        for(i=0;i<str.length();i++){
            if(s.pop()!=str.charAt(i))
                return false;
        }
        return true;
    }
}

复杂度：

时间复杂度：字符串长度为 $n$ ,平均时间复杂度为 $O(n)$
空间复杂度：利用辅助栈,栈大小不超过 $n$ , $O(n)$