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;
   }