7. DP_leetcode 5 Longest Palindromic Substring最長(zhǎng)回文子串

一块促、題目

Given a string S, find the longest palindromic substring in S.
You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
Example
Given the string = "abcdzdcab", return "cdzdc".
Challenge
O(n2) time is acceptable. Can you do it in O(n) time.
求一個(gè)字符串中的最長(zhǎng)回文子串。

二捺檬、解題思路

區(qū)間類動(dòng)態(tài)規(guī)劃

Time O(n^2), Space O(n^2)
用dp[i][j]來存DP的狀態(tài),需要較多的額外空間: Space O(n^2)
DP的4個(gè)要素
狀態(tài):
dp[i][j]: s.charAt(i)到s.charAt(j)是否構(gòu)成一個(gè)Palindrome
轉(zhuǎn)移方程:
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])
初始化:
dp[i][j] = true when j - i <= 2
結(jié)果:
找 maxLen = j - i + 1;龙亲,并得到相應(yīng)longest substring: longest = s.substring(i, j + 1);

中心擴(kuò)展

這種方法基本思想是遍歷數(shù)組锨阿,以其中的1個(gè)元素或者2個(gè)元素作為palindrome的中心,通過輔助函數(shù)交惯,尋找能拓展得到的最長(zhǎng)子字符串。外層循環(huán) O(n),內(nèi)層循環(huán)O(n)席爽,因此時(shí)間復(fù)雜度 Time O(n^2)意荤,相比動(dòng)態(tài)規(guī)劃二維數(shù)組存狀態(tài)的方法,因?yàn)橹恍枰孀铋L(zhǎng)palindrome子字符串本身只锻,這里空間更優(yōu)化:Space O(1)玖像。

三、解題代碼

區(qū)間DP齐饮,Time O(n^2) Space O(n^2)

public class Solution {
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
     public String longestPalindrome(String s) {
         if(s == null || s.length() <= 1) {
             return s;
         }

         int len = s.length();
         int maxLen = 1;
         boolean [][] dp = new boolean[len][len];

         String longest = null;
         for(int k = 0; k < s.length(); k++){
             for(int i = 0; i < len - k; i++){
                 int j = i + k;
                 if(s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])){
                     dp[i][j] = true;

                     if(j - i + 1 > maxLen){
                        maxLen = j - i + 1;
                        longest = s.substring(i, j + 1);
                     }
                 }
             }
         }

         return longest;
     }
}

Time O(n^2) Space O(1)

public class Solution {
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
    public String longestPalindrome(String s) {
            if (s.isEmpty()) {
                return null;
            }

            if (s.length() == 1) {
                return s;
            }

            String longest = s.substring(0, 1);
            for (int i = 0; i < s.length(); i++) {
                // get longest palindrome with center of i
                String tmp = helper(s, i, i);
                if (tmp.length() > longest.length()) {
                    longest = tmp;
                }

                // get longest palindrome with center of i, i+1
                tmp = helper(s, i, i + 1);
                if (tmp.length() > longest.length()) {
                    longest = tmp;
                }
            }

            return longest;
    }

    // Given a center, either one letter or two letter,
    // Find longest palindrome
    public String helper(String s, int begin, int end) {
        while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
            begin--;
            end++;
        }
        return s.substring(begin + 1, end);
    }
}

下一篇: 8. DP_01背包問題整理
上一篇: 6. DP_Maximum product Subarray

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末捐寥,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子祖驱,更是在濱河造成了極大的恐慌握恳,老刑警劉巖,帶你破解...
    沈念sama閱讀 221,695評(píng)論 6 515
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件捺僻,死亡現(xiàn)場(chǎng)離奇詭異乡洼,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)陵像,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,569評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門就珠,熙熙樓的掌柜王于貴愁眉苦臉地迎上來寇壳,“玉大人醒颖,你說我怎么就攤上這事】茄祝” “怎么了泞歉?”我有些...
    開封第一講書人閱讀 168,130評(píng)論 0 360
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)匿辩。 經(jīng)常有香客問我腰耙,道長(zhǎng),這世上最難降的妖魔是什么铲球? 我笑而不...
    開封第一講書人閱讀 59,648評(píng)論 1 297
  • 正文 為了忘掉前任挺庞,我火速辦了婚禮,結(jié)果婚禮上稼病,老公的妹妹穿的比我還像新娘选侨。我一直安慰自己,他們只是感情好然走,可當(dāng)我...
    茶點(diǎn)故事閱讀 68,655評(píng)論 6 397
  • 文/花漫 我一把揭開白布援制。 她就那樣靜靜地躺著,像睡著了一般芍瑞。 火紅的嫁衣襯著肌膚如雪晨仑。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,268評(píng)論 1 309
  • 那天,我揣著相機(jī)與錄音洪己,去河邊找鬼妥凳。 笑死,一個(gè)胖子當(dāng)著我的面吹牛答捕,可吹牛的內(nèi)容都是我干的猾封。 我是一名探鬼主播,決...
    沈念sama閱讀 40,835評(píng)論 3 421
  • 文/蒼蘭香墨 我猛地睜開眼噪珊,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼晌缘!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起痢站,我...
    開封第一講書人閱讀 39,740評(píng)論 0 276
  • 序言:老撾萬榮一對(duì)情侶失蹤磷箕,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后阵难,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體岳枷,經(jīng)...
    沈念sama閱讀 46,286評(píng)論 1 318
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,375評(píng)論 3 340
  • 正文 我和宋清朗相戀三年呜叫,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了空繁。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,505評(píng)論 1 352
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡朱庆,死狀恐怖盛泡,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情娱颊,我是刑警寧澤傲诵,帶...
    沈念sama閱讀 36,185評(píng)論 5 350
  • 正文 年R本政府宣布,位于F島的核電站箱硕,受9級(jí)特大地震影響拴竹,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜剧罩,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,873評(píng)論 3 333
  • 文/蒙蒙 一栓拜、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧惠昔,春花似錦幕与、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,357評(píng)論 0 24
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至营罢,卻和暖如春赏陵,著一層夾襖步出監(jiān)牢的瞬間饼齿,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,466評(píng)論 1 272
  • 我被黑心中介騙來泰國(guó)打工蝙搔, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留缕溉,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,921評(píng)論 3 376
  • 正文 我出身青樓吃型,卻偏偏與公主長(zhǎng)得像证鸥,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子勤晚,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,515評(píng)論 2 359

推薦閱讀更多精彩內(nèi)容