資訊專欄INFORMATION COLUMN
摘要：題目解析題目是要找出最長的回文字符串，拿到題目的第一反應(yīng)是遍歷子串，然后一直替換最長的子字符串即可了。但是這種解法遇到極端輸入狀況就會(huì)超時(shí)，指定的最長長度為，遍歷子串需要兩次循環(huán)，判斷回文需要一次循環(huán)，所以總的效率為，那么極端狀況會(huì)超時(shí)。
題目
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
題目是要找出最長的回文字符串，拿到題目的第一反應(yīng)是遍歷子串，然后一直替換最長的子字符串即可了。
但是這種解法遇到極端輸入狀況就會(huì)超時(shí)，指定的最長長度為1000，遍歷子串需要兩次循環(huán)，判斷回文需要一次循環(huán)，所以總的效率為O(n^3)，那么極端狀況會(huì)超時(shí)。
public String longestPalindrome(String s) {
String longestStr = "";
for(int start = 0 ; start= temp.length()){
continue;
}
if(checkStrValid(temp) && temp.length()>longestStr.length()){
longestStr = temp;
}
}
}
return longestStr;
}
private boolean checkStrValid(String s){
if(s==null || s.length()==0){
return false;
}
int start = 0 ,end = s.length()-1;
while(start < end){
if(s.charAt(start++)!=s.charAt(end--)){
return false;
}
}
return true;
}
正確解法
public String longestPalindrome2(String s) {
// parameter[0]保存start的值，parameter[1]保存maxLen的值
// 這樣定義變量是為了實(shí)現(xiàn)java引用傳遞
int[] parameter = new int[2];
for(int i = 0 ; i < s.length() ; ++i){
// 如果是奇數(shù)回文字符串，例如aba,bab,bbabb等
searchPalindrome(s , i , i ,parameter);
// 如果是偶數(shù)回文字符串，例如bbbb,baab,ceddec等
searchPalindrome(s , i , i+1 , parameter);
}
// 等價(jià)于s.subString(start , start + maxLen)
return s.substring(parameter[0],parameter[0] + parameter[1]);
}
private void searchPalindrome(String s , int left , int right , int[] parameter){
// 尋找回文字符串
while(left>=0 && right < s.length() && s.charAt(left) == s.charAt(right)){
--left;
++right;
}
// 如果maxLen < 構(gòu)造的回文子字符串長度
if(parameter[1] < right - left - 1){
// start = left + 1
parameter[0] = left + 1;
// maxLen = right - left - 1
parameter[1] = right - left - 1 ;
}
}
定義int[] parameter的原因是為了支持函數(shù)引用傳遞，以免在searchPalindrome改變int參數(shù)值回到longestPalindrome2方法中值又回到原來的值，這是java方法參數(shù)值傳遞特性導(dǎo)致的。該方法效率為O(n^2)。
其他解法還有一些比較巧妙的解法例如動(dòng)態(tài)規(guī)劃，馬拉車算法等，目前還不能理解其中的精髓，等到我學(xué)會(huì)本質(zhì)之后再補(bǔ)充，先貼個(gè)大神的博客放著。
https://www.cnblogs.com/grand...
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72505.html
摘要：難度題目是說給出一個(gè)字符串求出這個(gè)字符串的最長回文的子串回文是指前后完全對(duì)稱的字符串像是之類的都算是回文奇數(shù)字母的回文和偶數(shù)字母的回文中心是不一樣的奇數(shù)字母比如的中心在中間字母上偶數(shù)字母比如的回文在中間兩字母的中心上由此可見回文中心點(diǎn)實(shí)際上 Given a string s, find the longest palindromic substring in s. You may as...
摘要：回文的意思就是反轉(zhuǎn)字符串后和原字符串相等。因?yàn)檫@種想法沒次都是兩邊同時(shí)擴(kuò)展。所以要分目標(biāo)字符串長度為奇數(shù)目標(biāo)字符串為偶數(shù)兩種情況。 題目詳情 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.題目的意思是輸入...
摘要：一題目最長回文子串給定一個(gè)字符串，找到中最長的回文子串。你可以假設(shè)的最大長度為。示例輸入輸出注意也是一個(gè)有效答案。 一、題目 最長回文子串： 給定一個(gè)字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000。 示例 1： 輸入: babad輸出: bab注意: aba 也是一個(gè)有效答案。 示例 2： 輸入: cbbd輸出: bb 二、我的答案 思路 1.排...
摘要：這種解法中，外層循環(huán)遍歷的是子字符串的中心點(diǎn)，內(nèi)層循環(huán)則是從中心擴(kuò)散，一旦不是回文就不再計(jì)算其他以此為中心的較大的字符串。 Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length ...
摘要：暴力算法就是找到所有每個(gè)都進(jìn)行的檢查。時(shí)間復(fù)雜度是個(gè)調(diào)用平均時(shí)長為這里唯一確定用的是頭尾表示。因?yàn)榈膶?duì)稱性，我們可以從中間出發(fā)向兩邊延展，找到最長的分為兩種基本情況。奇數(shù)長度出發(fā)點(diǎn)一致，都為偶數(shù)長度出發(fā)點(diǎn)為相鄰的點(diǎn)，和結(jié)束是 Given a string s, find the longest palindromic substring in s. You may assume tha...
閱讀 1196·2021-11-24 09:38
閱讀 2604·2021-09-27 14:00
閱讀 1165·2019-08-30 15:55
閱讀 1340·2019-08-30 14:16
閱讀 1491·2019-08-30 10:54
閱讀 2865·2019-08-28 17:58
閱讀 758·2019-08-26 13:22
閱讀 1234·2019-08-26 12:01
