資訊專欄INFORMATION COLUMN
摘要：題目描述給定一個字符串，找到中最長的回文子串。你可以假設(shè)的最大長度為。示例輸入輸出注意也是一個有效答案。示例輸入輸出思路分析暴力解法解決一個問題如果沒有思路，就要想辦法從簡單粗暴的解法開始，然后想辦法優(yōu)化它。
題目描述
https://leetcode-cn.com/probl...
給定一個字符串 s，找到 s 中最長的回文子串。你可以假設(shè)?s 的最大長度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
示例 2：
輸入: "cbbd"思路分析 暴力解法
輸出: "bb"
解決一個問題如果沒有思路，就要想辦法從簡單粗暴的解法開始，然后想辦法優(yōu)化它。
以"babad"為例，
子串長度為1的時候，必然是回文
子串長度為2的時候，[ba,ab,ba,ad]，需要兩個字符串相等才是回文
子串長度為3的時候，[bab,aba,bad]，需要從兩邊向中心依次判斷字符是否相等
子串長度為4的時候，[baba,abad]。判斷方式同3
...
因此得到了一個暴力的解法，就是三層循環(huán)，
第一層循環(huán)是子串的長度規(guī)模(12345)
第二層循環(huán)是遍歷每個子串(ba ab ba ad)
第三層循環(huán)是對比首尾的字符是否相等
時間復雜度
$$ O(n^3) $$
空間復雜度
$$ O(1) $$
動態(tài)規(guī)劃子串長度為1的時候，必然是回文
子串長度為2的時候，[ba,ab,ba,ad]，需要兩個字符串相等才是回文
子串長度為3的時候，[bab,aba,bad]，需要從兩邊向中心依次判斷字符是否相等
子串長度為4的時候，[baba,abad]。判斷方式同3
...
基于暴力解法，我們發(fā)現(xiàn)3是可以復用1的結(jié)論的，4是可以復用2的結(jié)論的，5是可以復用3的結(jié)論的，因此就發(fā)現(xiàn)了DP的一個要素（重疊子問題）
DP的其它要素是最優(yōu)子結(jié)構(gòu)、子問題獨立，以及狀態(tài)轉(zhuǎn)移方程
狀態(tài)轉(zhuǎn)移方程：
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，這樣看之前的是否是回文，然后判斷子串的首尾兩個是否是回文
根據(jù)狀態(tài)轉(zhuǎn)移方程填寫dp數(shù)組，最后得到問題結(jié)果
時間復雜度
$$ O(n^2) $$
空間復雜度
$$ O(n^2) $$
中心擴展法然后再基于動態(tài)規(guī)劃解法的思路，分析下能否進一步縮小空間復雜度
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表示規(guī)格
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是偶數(shù)，說明中心點在一個字母上
m = i / 2;
n = i / 2;
} else {
// i是奇數(shù)，說明中心點在字母之間
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);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/76275.html
摘要：一題目最長回文子串給定一個字符串，找到中最長的回文子串。你可以假設(shè)的最大長度為。示例輸入輸出注意也是一個有效答案。 一、題目 最長回文子串： 給定一個字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000。 示例 1： 輸入: babad輸出: bab注意: aba 也是一個有效答案。 示例 2： 輸入: cbbd輸出: bb 二、我的答案 思路 1.排...
摘要：貪心算法每一步必須滿足一下條件可行的即它必須滿足問題的約束。四題目分析貪心算法，總是做出在當前看來是最好的選擇，不從整體最優(yōu)上加以考慮，也就是說，只關(guān)心當前最優(yōu)解，按照貪心策略，不關(guān)心以后，我們只關(guān)心當前利益。 一、寫在前面 為什么要在LeetCode刷題？大家都知道不管是校招還是社招算法題是必考題，而這一部分恰巧是大多數(shù)人的短板，所以刷題首先是為了提高自身的編程能力，能夠在算法面試中...
摘要：每天會折騰一道及以上題目，并將其解題思路記錄成文章，發(fā)布到和微信公眾號上。三匯總返回目錄在月日月日這半個月中，做了匯總了數(shù)組知識點?；蛘呃奖疚淖钕旅?，添加的微信等會根據(jù)題解以及留言內(nèi)容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...
摘要：第一種方法常規(guī)方法。如果不存在公共前綴，返回空字符串。注意假設(shè)字符串的長度不會超過。說明本題中，我們將空字符串定義為有效的回文串。示例輸入輸出一個可能的最長回文子序列為。數(shù)值為或者字符串不是一個合法的數(shù)值則返回。 說明 本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站點：https://www.weiweiblog.c...
摘要：用將子字符串轉(zhuǎn)化為，參見和的區(qū)別然后用動規(guī)方法表示字符串的前位到包含方法的個數(shù)。最后返回對應字符串末位的動規(guī)結(jié)果。 Problem A message containing letters from A-Z is being encoded to numbers using the following mapping: A -> 1 B -> 2 ... Z -> 26 Given ...
閱讀 1876·2021-11-25 09:43
閱讀 3705·2021-11-24 10:32
閱讀 1099·2021-10-13 09:39
閱讀 2347·2021-09-10 11:24
閱讀 3363·2021-07-25 21:37
閱讀 3481·2019-08-30 15:56
閱讀 876·2019-08-30 15:44
閱讀 1466·2019-08-30 13:18
