題目 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example:
Input: “babad”
Output: “bab” Note: “aba” is also a valid answer. Example: Input: “cbbd”
Output: “bb”
分析 尋找一個字符串的最長回文字串，題目很容易理解。很容易想到的解決辦法：把每個字母當(dāng)做回文串的中心字母，向兩半延伸判斷是否是回文串，并記錄下最長的字符串。時間復(fù)雜度為O(n^2) 這個比暴力求解要好，暴力求解是把所有字串找出來，然后判斷是否是回文串，時間復(fù)雜度為O(n^3)。
代碼
public String longestPalindrome(String s) { if(s.length()<=1) return s; int start = 0,len = 0 ; //從下標(biāo)為1的字符開始，把當(dāng)前字符當(dāng)做中心字符 向兩邊延伸判斷 for(int i = 1;i<s.length();i++){ //回文串長度為偶數(shù) int low = i-1,high = i ; while(low>=0 && high <s.length() && s.charAt(low) == s.charAt(high) ){ low --; high ++; } if(high - low- 1 > len){ len = high - low - 1; start = low +1; } //回文串長度為奇數(shù) low = i-1;high = i+1 ; while(low>=0 && high <s.length() && s.charAt(low) == s.charAt(high) ){ low --; high ++; } if( high - low - 1 > len){ len =high - low- 1; start = low +1; } } return s.substring(start,start+len); }將問題轉(zhuǎn)化為最長公共子串。 將s逆序存儲為s’，再求s與s’的最長公共子串。 比如： s = “cbab” s’=”babc” 最長公共子串為bab，也就是答案。 算法看這里
動態(tài)規(guī)劃算法 算法看這里
Manacher 算法 算法看這里
新聞熱點
疑難解答
