最长回文子串

1.题目描述

力扣题目链接

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

• 输入：s = “babad”
• 输出：“bab”
• 解释：“aba” 同样是符合题意的答案。

示例 2：

• 输入：s = “cbbd”
• 输出：“bb”

示例 3：

• 输入：s = “a”
• 输出：“a”

示例 4：

• 输入：s = “ac”
• 输出：“a”

2.解题

2.1解法一

暴力求解，但复杂度较高，会超出时间限制。

首先编写判断字符串是否为回文的函数，使用双指针法，分别从字符串的两段向中间遍历判断所选字符是否相等，如果相等则继续往中间遍历，否则返回false。

接着在主函数对输入的字符串使用双指针fromPointer和toPointer遍历，判断两个指针切割的字符串是否为回文且字符串长度是否最长，是回文且字符串长度最长，则记录该数据，否则进入下一次遍历。

时间复杂度判断：主函数双层循环，判断回文函数单层循环，复杂度为O(n^3)。

代码：

class Solution {
    public String longestPalindrome(String s) {
        //特殊情况处理
        if(s.length()==1){
            return s;
        }    


        //暴力遍历
        int fromPointer=0;
        int toPointer=fromPointer;
        int maxLengthTemp=0;   //记录中间结果
        String maxStringTemp="";

        for(fromPointer=0;fromPointer<s.length();fromPointer++){
            toPointer=fromPointer; 
            while(toPointer<=s.length()-1){
                String temp=s.substring(fromPointer,toPointer+1);  //java String api书写：注意substring s不用大写
                if(ispalindrome(temp)&&temp.length()>maxLengthTemp){
                    maxLengthTemp=temp.length();
                    maxStringTemp=temp;
                    toPointer++;
                }else{
                     toPointer++;
                }
            }
        }
        return maxStringTemp;
    }

    //判断是否为回文
    public boolean ispalindrome(String str){
        int i=0;
        int j=str.length()-1;
        if(i==j){
            return true;
        }
        boolean result=true;
        while(i<j){
            if(str.charAt(i)!=(str.charAt(j))){
                return false;
            }else{
                i++;
                j--;
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

2.2解法二

采用dp思想。相关步骤介绍见代码随想录。

时间复杂度：O(n^2)

空间复杂度：O(n^2)

代码：

class Solution {
    public String longestPalindrome(String s) {
        int maxLen=0;
        int fromPointer=0;
        int toPointer=0;

        int len=s.length();
        //特殊情况处理
        if(len==1){
            return s;
        }   

        boolean dp[][]=new boolean[len][len]; //默认初始化元素都为false
        //构造dp矩阵
        for(int i=0;i<len;i++){
            dp[i][i]=true;
        }

        //矩阵的右上角元素需要借助左下角元素，因此应从下至上，从左至右变量dp矩阵
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){
                if(s.charAt(i)!=s.charAt(j)){
                    dp[i][j]=false;
                }else{
                      if(j-i<=2){      //example:aba;ab 这种情况无需看其子串
                        dp[i][j]=true;
                    }else{
                        dp[i][j]=dp[i+1][j-1];
                    }
                }

                //记录最长回文子串的索引
                if(dp[i][j]&&j-i+1>maxLen){
                    maxLen=j-i+1;
                    fromPointer=i;
                    toPointer=j;
                }
            }
        }

        return s.substring(fromPointer,toPointer+1);

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

2.3解法三

双指针法：

两种情况：

一个元素从中间向两侧扩张，判断是否为回文，覆盖了字符串中字符个数为偶数的情况。

两个元素从中间向两侧扩张，判断是否为回文，覆盖了字符串中字符个数为奇数的情况。

时间复杂度：O(n^2)

空间复杂度：O(1)

class Solution {
    public String longestPalindrome(String s) {
    
        int[] temp={0,0,1}; //fromPointer toPointer maxLen 

        if(s.length()==1){
            return s;
        }

       for(int i=0;i<s.length();i++){   
           extend(i,i,temp,s);  //分奇偶
           extend(i,i+1,temp,s);
       }

       return s.substring(temp[0],temp[1]+1);

    }

       public void extend(int i,int j,int []temp,String s){
           while(i>=0 && j<s.length() && s.charAt(i)==s.charAt(j)){
               if(j-i+1>temp[2]){
                   temp[0]=i;
                   temp[1]=j;
                   temp[2]=j-i+1;
               }
               i--;
               j++;
           }
       }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30