LeetCode 5. Longest Palindromic Substring題解

文章目錄

• 題目
• • 5. Longest Palindromic Substring
• 分析
• • 思路一：動态規劃
  • 思路二：（從中央位置開始）雙向擴充掃描
• 題解
• • 思路一Java實作
  • 思路二Java實作

題目

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
           

Example 2:

Input: "cbbd"
Output: "bb"
           

分析

思路一：動态規劃

定義狀态：

       dp[i][j]：從index=i到index=j（包括i,j）的一段子串是否是回文串；

       dp[i][j] = true：是回文串；

       dp[i][j] = false：不是回文串。

定義轉移方程：

       dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]) （條件：i+1 <= j-1）

       dp[i][j] = s[i] == s[j] （條件：i+1 > j-1）

定義初始值：

       dp[s.length()-1][s.length()-1] = true;

思路二：（從中央位置開始）雙向擴充掃描

對于串s的長度，分為奇數與偶數兩種情況來考慮：

       奇數情況下，中心位置是一個字元；

       偶數情況下，中心位置是兩個字元之間的間隙。

實作思路：從頭開始周遊字元串s的每個字元，找到所有可作中心點的位置，對每個位置進行一次“雙向擴充掃描”，找到以該位置為中心的最長回文子串。

題解

思路一Java實作

public class Solution {

    public String longestPalindrome(String s) {
        int length = s.length();

        //處理字元串為空的特殊情況
        if(length<1)return "";

        //存儲最長的回文子串的起始結束位置（兩端包含）
        int maxBegin = 0;
        int maxEnd = 0;

        //要傳回的最長子串
        String longestPalindrome = "";

        boolean dp[][] = new boolean[length+1][length];

        //設定初始值
        dp[length-1][length-1] = true;

        for(int begin=length-1;begin>=0;begin--){
            for(int end=length-1;end>=begin;end--){

                //轉移方程
                if(s.charAt(begin)==s.charAt(end)){
                    if(end-1<=begin+1 || dp[begin+1][end-1]){
                        dp[begin][end] = true;
                        //System.out.println("dp[" + i + "][" + j + "] = true");

                        //與目前已經記錄下來的最長子串作對比（取相對更長的那一個）
                        if(end-begin>maxEnd-maxBegin){
                            maxBegin = begin;
                            maxEnd = end;
                        }
                        continue;
                    }
                    dp[begin][end] = false;
                    //System.out.println("dp[" + i + "][" + j + "] = false");
                }
            }
        }
        return s.substring(maxBegin,maxEnd+1);
    }

//    public static void main(String[] args) {
//        System.out.println(new Solution().longestPalindrome("cbbd"));
//    }
}
           

思路二Java實作

public class Solution2 {

    public String longestPalindrome(String s) {
        String longestPalindrome = "";
        for (int i = 0; i < s.length(); i++) {
            //奇數情況
            int pre = i;
            int next = i;
            String s1 = getLongestPalindromeByIndex(pre, next, s);
            //偶數情況
            next++;
            String s2 = getLongestPalindromeByIndex(pre, next, s);
            s1 = s1.length() > s2.length() ? s1 : s2;
            longestPalindrome = longestPalindrome.length() >= s1.length() ? longestPalindrome : s1;
        }
        return longestPalindrome;
    }

    public static String getLongestPalindromeByIndex(int pre, int next, String s) {
        while (pre >= 0 && next < s.length() && s.charAt(pre) == s.charAt(next)) {
            pre--;
            next++;
        }
        //當退出循環時，說明目前pre和next不相等，從pre+1截取到next-1
        return s.substring(pre + 1, next);
    }
}