首页 > 代码库 > [LeetCode] 5. Longest Palindromic Substring ☆☆☆☆
[LeetCode] 5. Longest Palindromic Substring ☆☆☆☆
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"
解法1:
遍历每个字符,以该字符为中心,往两边扩散寻找回文子串。应注意奇偶情况,比如"bob"是奇数形式的回文,"noon"就是偶数形式的回文,两种形式的回文都要搜索。该算法时间复杂度为O(n2)。
public class Solution { public String longestPalindrome(String s) { int maxBegin = 0; // 最大回文子串的起始点 int maxLength = 0; // 最大回文子串的长度 int currLength = 0; // 以当前字符为中心的回文子串长度 for (int i = 0; i < s.length() - 1; i++) { // 以当前字符为中心寻找回文子串 currLength = searchPalindrome(s, i, i); if (currLength > maxLength) { maxLength = currLength; maxBegin = i - (currLength >> 1); } // 如果当前字符和下一个字符相同,还应寻找以这两个字符为中心的回文子串 if (s.charAt(i) == s.charAt(i + 1)) { currLength = searchPalindrome(s, i, i + 1); if (currLength > maxLength) { maxLength = currLength; maxBegin = i + 1 - (currLength >> 1); } } } if (maxLength == 0) maxLength = s.length(); return s.substring(maxBegin, maxBegin + maxLength); } public int searchPalindrome(String s, int left, int right) { int step = 1; while ((left - step >= 0) && (right + step < s.length())) { if (s.charAt(left - step) != s.charAt(right + step)) break; step++; } return right - left + (step << 1) - 1; } }
解法2:
此题还可以用动态规划Dynamic Programming来解,我们维护一个二维数组dp,其中dp[i][j]表示字符串区间[i, j]是否为回文串,当i = j时,只有一个字符,肯定是回文串,如果i = j + 1,说明是相邻字符,此时需要判断s[i]是否等于s[j],如果i和j不相邻,即i - j >= 2时,除了判断s[i]和s[j]相等之外,dp[j + 1][i - 1]若为真,就是回文串,通过以上分析,可以写出递推式如下:
dp[i, j] = 1 if i == j
= s[i] == s[j] if j = i + 1
= s[i] == s[j] && dp[i + 1][j - 1] if j > i + 1
判断顺序:s[0][0] —> s[0][1] —> s[1][1] —> s[0][2] —> s[1][2] —> s[2][2] —> s[0][3] —> ....
public class Solution { public String longestPalindrome(String s) { boolean[][] isPal = new boolean[s.length()][s.length()]; int left = 0; int right = 0; for (int j = 0; j < s.length(); j++) { for (int i = 0; i < j; i++) { isPal[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i < 2 || isPal[i + 1][j - 1]); if (isPal[i][j] && (j - i > right - left)) { left = i; right = j; } } isPal[j][j] = true; } return s.substring(left, right + 1); } }
解法3:
最后要来的就是大名鼎鼎的马拉车算法Manacher‘s Algorithm,这个算法的神奇之处在于将时间复杂度提升到了O(n)这种逆天的地步,而算法本身也设计的很巧妙,很值得掌握,具体算法参见:Manacher算法总结 和 Manacher‘s Algorithm 马拉车算法。
public class Solution { public String longestPalindrome(String s) { // 字符串穿插"#",同时加头加尾防止越界 StringBuilder sb = new StringBuilder("@#"); for (int i = 0; i < s.length(); i++) { sb.append(s.charAt(i)).append("#"); } sb.append("$"); int[] len = new int[sb.length()]; int maxCenter = 0; // 记录最大回文子串的中心位置 int maxLength = 0; // 记录最大回文子串的半径 int id = 0; // 记录当前计算过的右边界所属的回文子串中心 int mx = 0; // 记录当前计算过的右边界 for (int i = 1; i < sb.length() - 1; i++) { len[i] = i < mx ? Math.min(len[2 * id - i], mx - i + 1) : 1; while (sb.charAt(i - len[i]) == sb.charAt(i + len[i])) len[i]++; if (mx < i + len[i] - 1) { mx = i + len[i] - 1; id = i; } if (maxLength < len[i]) { maxLength = len[i]; maxCenter = i; } } return s.substring((maxCenter - maxLength) / 2, (maxCenter - maxLength) / 2 + maxLength - 1); } }
[LeetCode] 5. Longest Palindromic Substring ☆☆☆☆