Leetcode —— 5. 最長回文子串

• 描述

  給你一個字元串 s，找到 s 中最長的回文子串。

• 示例 1：

  輸入：s = “babad”

  輸出：“bab”

  解釋：“aba” 同樣是符合題意的答案。

• 示例 2：

  輸入：s = “cbbd”

  輸出：“bb”

• 示例 3：

  輸入：s = “a”

  輸出：“a”

• 示例 4：

  輸入：s = “ac”

  輸出：“a”

• 提示：

  1 <= s.length <= 1000

  s 僅由數字和英文字母（大寫和/或小寫）組成

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/longest-palindromic-substring

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

• 題解 : 動态規劃

public String longestPalindrome(String s) {
        int len = s.length();
       if (len < 2) {
           return s;
       }

        //狀态容器
        boolean[][] dp = new boolean[len][len];
        for ( int i = 0; i < len ; i++){
            dp[i][i] = true;
        }

        int max = 1, start = 0;
        char[] c = s.toCharArray();

        for (int j = 1; j < len; j++){ // j的範圍[1,len-1]
            for ( int i = 0; i < len - 1 && i < j; i++){ // i的範圍[0,len-2]
                if (c[i] != c[j]) {
                    dp[i][j] = false;
                } else{
                    if(j - i < 3){  // i
                        dp[i][j] = true;
                    } else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                if(dp[i][j] && j - i + 1 > max){
                    max = j - i + 1;
                    start = i;
                }
            }
        }


        return s.substring(start,start + max);
    

    }
           

• 題解：暴力算法

public String longestPalindrome(String s) {
        // 暴力解法
        int length = s.length();
        if(length < 2){
            return s;
        }

        char[] arr = s.toCharArray();
        int max = 1;
        int begin = 0;
        // 枚舉所有長度大于1的字串 charArray[i..j]
        for(int i = 0; i < length -1; i++){
            for (int j = i + 1; j < length; j++){
                if(max < j - i + 1 && validStr(arr,i, j)){
                    max = j - i + 1;
                    begin = i;
                }
            }
        }
        
        return s.substring(begin, begin + max);
    }

    /**
     * 驗證字串 s[left..right] 是否為回文串
     */

    private boolean validStr(char[] arr, int left, int right){
        while (left < right){
            if(arr[left] != arr[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    
    }
           

• 題解： 中心擴散法

public String longestPalindrome(String s) {
       int length = s.length();
       if(length < 2){
           return s;
       }

       int maxLen = 1;
       int begin = 0;

       char[] charArray = s.toCharArray();
       //選取中心點 舍去最右邊的
       for (int i = 0; i < length - 1; i++) {
           int oddLen = expandAroundCenter(charArray, i, i);
           int evenLen = expandAroundCenter(charArray, i, i + 1);

           int curMaxLen = Math.max(oddLen, evenLen);
           if (curMaxLen > maxLen) {
               maxLen = curMaxLen;
               // 規律 已知中心點和長度 求 開始點
               begin = i - (maxLen - 1) / 2;
           }

       }
       return s.substring(begin, begin + maxLen);
   }

   /**
    *
    * @param arr 原始字元串的字元數組
    * @param left 起始左邊界（可以取到）
    * @param right 起始右邊界（可以取到）
    * @return 回文串的長度
    */
   private int expandAroundCenter(char[] arr, int left, int right) {
       // 當 left = right 的時候，回文中心是一個字元串，回文串的長度是奇數
       // 當 left = right + 1 的時候，回文中心是一個字元串，回文串的長度是偶數
       int len = arr.length;
       int i = left;
       int j = right;
       while(i >= 0 && j < len){
           if(arr[i] == arr[j]){
               i--;
               j++;
           }else {
               break;
           }
       }
       // 跳出 while 循環時，恰好滿足 s.charAt(i) != s.charAt(j)
       // 回文串的長度是 j - i + 1 - 2 = j - i - 1
       return j - i - 1;
   }