LeetCode代碼分析——5. longest-palindromic-substring（動態規

neuSnail 發布于2019-08-19 10:35 / 3669人閱讀

摘要：題目描述給定一個字符串，找到中最長的回文子串。你可以假設的最大長度為。示例輸入輸出注意也是一個有效答案。示例輸入輸出思路分析暴力解法解決一個問題如果沒有思路，就要想辦法從簡單粗暴的解法開始，然后想辦法優化它。

題目描述

https://leetcode-cn.com/probl...

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

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。

示例 2：

輸入: "cbbd"
輸出: "bb"

思路分析 暴力解法

解決一個問題如果沒有思路，就要想辦法從簡單粗暴的解法開始，然后想辦法優化它。
以"babad"為例，

子串長度為1的時候，必然是回文

子串長度為2的時候，[ba,ab,ba,ad]，需要兩個字符串相等才是回文

子串長度為3的時候，[bab,aba,bad]，需要從兩邊向中心依次判斷字符是否相等

子串長度為4的時候，[baba,abad]。判斷方式同3

...

因此得到了一個暴力的解法，就是三層循環，

第一層循環是子串的長度規模(12345)

第二層循環是遍歷每個子串(ba ab ba ad)

第三層循環是對比首尾的字符是否相等

時間復雜度

$$ O(n^3) $$

空間復雜度

$$ O(1) $$

動態規劃

子串長度為1的時候，必然是回文

子串長度為2的時候，[ba,ab,ba,ad]，需要兩個字符串相等才是回文

子串長度為3的時候，[bab,aba,bad]，需要從兩邊向中心依次判斷字符是否相等

子串長度為4的時候，[baba,abad]。判斷方式同3

...

基于暴力解法，我們發現3是可以復用1的結論的，4是可以復用2的結論的，5是可以復用3的結論的，因此就發現了DP的一個要素（重疊子問題）
DP的其它要素是最優子結構、子問題獨立，以及狀態轉移方程

狀態轉移方程：
dpi表示子串長度為i時，從j開頭的子串是否為回文
s表示字符串

$$ dp[i][j] = egin{equation} egin{cases} true,&i=1 s[j] == s[j+1],&i=2 dp[i-2][j] && s[j]==s[j+i],&其它 end{cases} end{equation} $$

長度為1的時候必然是回文，
長度為2的時候取決于前后兩個字符串是否相等
其它情況則3看1,4看2，這樣看之前的是否是回文，然后判斷子串的首尾兩個是否是回文

根據狀態轉移方程填寫dp數組，最后得到問題結果

時間復雜度

$$ O(n^2) $$

空間復雜度

$$ O(n^2) $$

中心擴展法

然后再基于動態規劃解法的思路，分析下能否進一步縮小空間復雜度
todo

源碼 動態規劃

public class MyDpSolution {

    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return "";
        }
        boolean[][] dp = new boolean[s.length()][s.length()];
        for(int i = 0; i < s.length(); i++) {
            // i表示規格
            for(int j = 0; j < s.length() - i; j++){
                if(i == 0){
                    dp[i][j] = true;
                } else if(i == 1) {
                    dp[i][j]= s.charAt(j) == s.charAt(j+1);
                } else {
                    dp[i][j] = s.charAt(j) == s.charAt(j+i) && dp[i-2][j+1];
                }
            }
        }
        for(int i = s.length() - 1; i >= 0; i--) {
            for(int j = 0; j + i < s.length(); j++) {
                if(dp[i][j]) {
                    return s.substring(j, j + i + 1);
                }
            }
        }
        return "";
    }

}

中心擴展法

public class MyCenterExternSolution {

    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return "";
        }
        if(s.length() == 1) {
            return s;
        }
        int max_m = 0;
        int max_n = 0;
        int max = 0;
        for(int i = 1; i < s.length() * 2; i++) {
            int m,n,len=0;
            if((i & 1) == 0) {
                // i是偶數，說明中心點在一個字母上
                m = i / 2;
                n = i / 2;
            } else {
                // i是奇數，說明中心點在字母之間
                m = (i - 1) / 2;
                n = (i + 1) / 2;
            }
            while(m >= 0 && n < s.length() && s.charAt(m) == s.charAt(n)) {
                m--;
                n++;
                len = n - m;
            }
            if(len > max) {
                max = len;
                max_m = m+1;
                max_n = n-1;
            }
        }
        return s.substring(max_m, max_n + 1);
    }

}

GPU云服務器云服務器有違規 LeetCode LeetCode_String 代碼動態

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76275.html

LeetCode.5 最長回文子串(longest-palindromic-substring)(J

摘要：一題目最長回文子串給定一個字符串，找到中最長的回文子串。你可以假設的最大長度為。示例輸入輸出注意也是一個有效答案。一、題目最長回文子串：給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。示例 1：輸入: babad輸出: bab注意: aba 也是一個有效答案。示例 2：輸入: cbbd輸出: bb 二、我的答案思路 1.排...

Steven 2019-08-23 16:47 評論0 收藏0
【LeetCode】貪心算法--買賣股票的最佳時機 II（122）

摘要：貪心算法每一步必須滿足一下條件可行的即它必須滿足問題的約束。四題目分析貪心算法，總是做出在當前看來是最好的選擇，不從整體最優上加以考慮，也就是說，只關心當前最優解，按照貪心策略，不關心以后，我們只關心當前利益。一、寫在前面為什么要在LeetCode刷題？大家都知道不管是校招還是社招算法題是必考題，而這一部分恰巧是大多數人的短板，所以刷題首先是為了提高自身的編程能力，能夠在算法面試中...

xbynet 2019-07-31 11:21 評論0 收藏0
LeetCode 攻略 - 2019 年 8 月上半月匯總（109 題攻略）

摘要：每天會折騰一道及以上題目，并將其解題思路記錄成文章，發布到和微信公眾號上。三匯總返回目錄在月日月日這半個月中，做了匯總了數組知識點。或者拉到本文最下面，添加的微信等會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

tracy 2019-08-26 10:49 評論0 收藏0
[算法總結] 搞定 BAT 面試——幾道常見的子符串算法題

摘要：第一種方法常規方法。如果不存在公共前綴，返回空字符串。注意假設字符串的長度不會超過。說明本題中，我們將空字符串定義為有效的回文串。示例輸入輸出一個可能的最長回文子序列為。數值為或者字符串不是一個合法的數值則返回。說明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站點：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 評論0 收藏0
[LintCode/LeetCode] Decode Ways [String to Integer

摘要：用將子字符串轉化為，參見和的區別然后用動規方法表示字符串的前位到包含方法的個數。最后返回對應字符串末位的動規結果。 Problem A message containing letters from A-Z is being encoded to numbers using the following mapping: A -> 1 B -> 2 ... Z -> 26 Given ...

andong777 2019-08-14 15:44 評論0 收藏0