Leetcode第5题 最长回文子串

题目描述

https://leetcode.cn/problems/longest-palindromic-substring/

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

个人思路

首先判断写一个判断回文的函数，然后从中间开始向左或者向右遍历判断下一个字符是否为回文（即[0,n-2]相当于中心点向左偏移），如果为回文则直接返回，因为中间的回文最长。

    public String judge(String s){
        if(s.length()<=1)return s;
        if(s.length()==2)return s.charAt(0)==s.charAt(1)?s:String.valueOf(s.charAt(0));
        int i=s.length()/2;
        int j=0;

        StringBuilder stringBuilder=new StringBuilder("");
        if(i%2==0){
            while (i>0 && i-j-1 >=0  && i+j<=s.length()){
                if(s.charAt(i+j)==s.charAt(i-j-1)){
                    stringBuilder.append(s.charAt(i-j));
                    j++;
                }else {
                    break;
                }
            }
        }else {
            while (i>0 && i-j >=0  && i+j<=s.length()){
                if(s.charAt(i-j)==s.charAt(i+j)){
                    stringBuilder.append(s.charAt(i-j));
                    j++;
                }else {
                    break;
                }
            }
        }

        StringBuilder x=new StringBuilder("");

        for(int l=1;l<stringBuilder.length();l++){
            x.append(stringBuilder.charAt(l));
        }
        if(s.length()%2==0){
            x.append(stringBuilder.charAt(0));
        }
        x.append(stringBuilder);
        return x.toString();
    }
    public String longestPalindrome(String s) {
        if(s.length()<=1)return s;
        if(s.length()==2)return s.charAt(0)==s.charAt(1)?s:String.valueOf(s.charAt(0));

        int i=s.length()/2;
        int sum=0;
        String s1="";
        String temp=judge(s);
        if(temp.length()>sum){
            sum=temp.length();
            s1=temp;
        }

        for(int j=0;j<s.length()/2;j++){
            //        left
            temp = s.substring(j*2,s.length());
            temp =judge(temp);
            if(temp.length()>sum){
                sum=temp.length();
                s1=temp;
            }
            //        right
            temp=s.substring(0,s.length()-j*2);
            temp =judge(temp);
            if(temp.length()>=sum){
                sum=temp.length();
                s1=temp;
            }
        }
        temp=s.substring(0,2);
        temp = judge(temp);
        if(temp.length()>sum){
            sum=temp.length();
            s1=temp;
        }
        temp=s.substring(s.length()-2);
        temp = judge(temp);
        if(temp.length()>sum){
            sum=temp.length();
            s1=temp;
        }
        return  s1;
    }

代码优化

原代码思路特别长，为此做出优化。

1. 判断回文的方式进行修改，返回变成下标，而不是直接返回回文字符，方便判断

    public int expandAroundCenter(String s, int left, int right) {
               while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                   --left;
                   ++right;
               }
               return right - left - 1;
           }

   1. 弃用改变中心点的位置，直接改左右字符串开始的位置

      public String longestPalindrome(String s) {
                  if (s == null || s.length() < 1) {
                      return "";
                  }
                  int start = 0, end = 0;
                  for (int i = 0; i < s.length(); i++) {
                      int len1 = expandAroundCenter(s, i, i);
                      int len2 = expandAroundCenter(s, i, i + 1);
                      int len = Math.max(len1, len2);
                      if (len > end - start) {
                          start = i - (len - 1) / 2;
                          end = i + len / 2;
                      }
                  }
                  return s.substring(start, end + 1);
              }

      其他方法

      动态规划

      dp[i][j]表示从i到j是一个回文，如果dp[i][j]要是回文，则需要s[i]==s[j],并且dp[i][j]=dp[i+1,j-1],如图所示。

      

      public class Solution {
      
          public String longestPalindrome(String s) {
              if (s.length() < 2) return s;
              int maxLen = 1;
              int begin = 0;
              // dp[i][j] 表示 s[i, j] 是否是回文串
              boolean[][] dp = new boolean[len][len];
              // 使用将字符串传为字符数组，使得每次不需要进行chatAt()
              char[] charArray = s.toCharArray();
              for (int i = 0; i < len; i++) {
                  dp[i][i] = true;
              }
              for (int j = 1; j < len; j++) {
                  for (int i = 0; i < j; i++) {
                      if (charArray[i] != charArray[j]) {
                          dp[i][j] = false;
                      } else {
                          // 长度为3，两边相同即回文
                          if (j - i < 3) {
                              dp[i][j] = true;
                          } else {
                              dp[i][j] = dp[i + 1][j - 1];
                          }
                      }
                      // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，记录回文长度和起始位置
                      if (dp[i][j] && j - i + 1 > maxLen) {
                          maxLen = j - i + 1;
                          begin = i;
                      }
                  }
              }
              return s.substring(begin, begin + maxLen);
          }
      }