题目是:找出一个字符串中的最长回文子串。
例如:abcbcbb的最长回文子串是bcbcb
首先一种常见的错误方法是把原字符串S倒转过来成为S‘,以为这样就将问题转化成为了求S和S’的最长公共子串的问题。反例S="abacdfgdcaba",若按这种解法得到答案是:"abacd",显然不是回文,而正确答案是"aba"
PS:这也是LeetCode的一道题:http://blog.csdn.net/fightforyourdream/article/details/15025663
下面总结一下四种解法:(面试时推荐中心展开法)
1)暴力法:Time:O(n^3), Space:O(1)
2)DP法:Time:O(n^2), Space:O(n^2)
http://faculty.utpa.edu/liuy2/algorithmGroup.html
3)中心展开法:Time:O(n^2), Space:O(n) ***推荐面试时用!!!
http://blog.163.com/zhaohai_1988/blog/static/2095100852012716105847112/
4)Manacher算法:Time:O(n),Space: O(n) (精妙但较麻烦)
http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
下面是实现代码:
package String;
public class LongestPalindromeSubstring {
// 暴力法 Time Complexity: O(n^3)
public static String longestPalindromeBruteForce(String s) {
String longest = "";
if(s.isEmpty()) {
return longest;
}
for(int i=0; i<s.length(); i++) { // 开始位置
for(int j=i; j<s.length(); j++) { // 结束位置
String substr = s.substring(i, j+1);
if(j-i+1 > longest.length() && isPalindrome(substr)) {
longest = substr;
}
}
}
return longest;
}
// O(n) 检查是否为回文
private static boolean isPalindrome(String s) {
int len = s.length();
for(int i=0; i<=len/2; i++) {
if(s.charAt(i) != s.charAt(len-1-i)) {
return false;
}
}
return true;
}
// ===========================================
// 动态规划1 时间复杂度O(N2), 空间复杂度O(N2)
public static String longestPalindromeDP1(String s) {
int len = s.length();
int longestBegin = 0;
int maxLen = 1;
boolean[][] isPalindrome = new boolean[len+1][len+1];
for(int i=0; i<len; i++) {
isPalindrome[i][i] = true;
}
for(int i=0; i<len-1; i++) {
if(s.charAt(i) == s.charAt(i+1)) {
isPalindrome[i][i+1] = true;
longestBegin = i;
maxLen = 2;
}
}
for(int l=2; l<=len; l++) { // 回文子串的长度
for(int i=0; i<len-l+1; i++) { // 回文子串的开始位置
int j = i+l-1; // 回文子串的结束位置
if(isPalindrome[i+1][j-1] && s.charAt(i) == s.charAt(j)) {
isPalindrome[i][j] = true;
longestBegin = i;
maxLen = l;
}
}
}
return s.substring(longestBegin, longestBegin+maxLen);
}
// ===========================================
// 中心展开法 时间复杂度O(N2), 空间复杂度O(1)
public static String longestPalindromeExpand(String s) {
int len = s.length();
if(len == 0) {
return "";
}
String longest = s.substring(0, 1);
for(int i=0; i<len; i++) {
// 当回文为奇数长度时
String p1 = expandAroundCenter(s, i, i);
if(p1.length() > longest.length()) {
longest = p1;
}
// 当回文为偶数长度时
String p2 = expandAroundCenter(s, i, i+1);
if(p2.length() > longest.length()) {
longest = p2;
}
}
return longest;
}
// c1, c2为展开的中心位置
private static String expandAroundCenter(String s, int c1, int c2) {
int l = c1, r = c2;
int len = s.length();
// 如果检查位置相等,则分别往左右展开
while(l>=0 && r<=len-1 && s.charAt(l)==s.charAt(r)) {
l--;
r++;
}
return s.substring(l+1, r); // 回文子串
}
// ===========================================
// Manacher算法, Time: O(N), Space: O(N)
// http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
public static String longestPalindromeManacher(String s) {
String T = preProcess(s);
int len = T.length(); // 经过变化后,len总是为奇数长
int[] P = new int[len]; // P数组存放在某index下的回文半径长度
int C = 0, R = 0; // C为最长回文子串的中心位置,R为当前最长回文子串的右边界位置
for(int i=1; i<len-1; i++) {
int iMirror = C - (i-C); // 计算i的对应回文左边匹配位置i'
/*
if (R - i > P[iMirror])
P[i] = P[iMirror];
else // P[iMirror] >= R - i
P[i] = R - i; // P[i] >= R - i,取最小值,之后再匹配更新。
可简写成P[i] = (R > i) ? Math.min(R-i, P[iMirror]) : 0;
*/
P[i] = (R > i) ? Math.min(R-i, P[iMirror]) : 0;
// 贪心拓展以i为回文中心的回文子串
while(T.charAt(i+1+P[i]) == T.charAt(i-1-P[i])) {
P[i]++;
}
// 如果以i为中心的回文扩展超过了R,则我们找到一个新的更长回文子串
// 因此 更新 最长回文子串的中心和右边界
if(P[i] > R-i) {
C = i;
R = i + P[i];
}
}
// 现在P[i]数组里存放了以i为中心的回文子串长度,用打擂台方式找到最长者
int maxLen = 0;
int centerIndex = 0;
for(int i=1; i<len-1; i++) {
if(P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
int start = (centerIndex-1-maxLen)/2;
int end = start + maxLen;
return s.substring(start, end);
}
// 把s转换成T,如s="abba",则T="^#a#b#b#a#$"
// ^和$加在字符串首尾用来避免边界检查
private static String preProcess(String s) {
int len = s.length();
if(len == 0) {
return "^$";
}
String ret = "^";
for(int i=0; i<len; i++) {
ret += "#" + s.substring(i, i+1);
}
ret += "#$";
return ret;
}
public static void main(String[] args) {
// String s = "abacdfgdcaba";
String s = "abcbcbb";
System.out.println(longestPalindromeBruteForce(s));
System.out.println(longestPalindromeDP1(s));
System.out.println(longestPalindromeExpand(s));
System.out.println(longestPalindromeManacher(s));
}
}
最后:
这道题其实还可以用后缀树(Suffix Tree)来做,但是复杂度(O(nlogn))超过Manacher算法,并且实现起来更加麻烦,所以暂时没添加进来。
分享到:
相关推荐
最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container With Most Water 盛最多水的容器 13 Roman to Integer 罗马数字转整数 14 Longest Common Prefix 最长公共前缀 20 Valid ...
最长回文子串 6. ZigZag Conversion Z字型变换 7. Reverse Integer 整数反转 8. String to Integer (atoi) 字符串转换整数 (atoi) 9. Palindrome Number 回文数 10. Regular Expression Matching 正则表达式匹配 11....
最长回文子串 Longest Palindromic Substring.cpp 7 整数反转 Reverse Integer.cpp 9 回文数 Palindrome Number.cpp 12 整数转罗马数字 Integer to Roman.cpp 13 罗马数字转整数 Roman to Integer.cpp 15 三数之和 3...
最长回文子串,补符号,记忆 6. ZigZag Conversion 观察规律 7. Reverse Integer 翻转整数 8. String to Integer 解析字符串 9. Palindrome Number 回文数字 10. Regular Expression Matching 动态规划,列出转换...
最长回文子串,Manacher算法 0010 RegularExpressionMatching :star: :star: :star: 正则表达式匹配,dp 0012 Integer to Roman :star: 数组 0013 Roman to Integer :star: 哈希表 0014 Longest Common Prefix :star...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
Leetcode回文串拼接 leetcode_node 题解 该项目主要用于基于Leetcode的刷题记录,与日常学习,对Leetcode上的题目按照解题方法进行分明别类的整理。 题目列表 1.Two Sum 2.Add Two Numbers 3.Longest Substring ...
far_pos表示最长回文字符串的最大边界距离,ci表示最长回文字符串的中心位置, 状态数据dp[i] 表示i位置的回文串半径 j = min(far_pos - i + 1, dp[2*ci-i]) 8. String to Integer (atoi) 字符串前置空格先去除,然后...
LeetCode刷题总结 1.Two Sum 2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7....
回文 ZigZag Conversion 中等 矩阵 重要 Reverse Integer 简单 字串 String to Integer (atoi) 中等 字串 麻烦 Palindrome Number 简单 字串 Container With Most Water 中等 动态规划 重要 Integer to Roman 中等 ...
Palindrome Number 11. Container With Most Water 12. Integer to Roman 13. Roman to Integer 14. Longest Common Prefix 15. 3Sum 20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses ...
leetcode Python 001 leetcode的算法问题 ...Palindrome Number 010. Regular Expression Matching 011. Container With Most Water 012. Integer to Roman 013. Roman to Integer 014. Longest Common Prefix 019. R
Palindrome Number 简单 11 Container With Most Water 中等 12 Integer to Roman 中等 13 Roman to Integer 简单 14 Longest Common Prefix 简单 15 3Sum 中等 16 3Sum Closest 中等 17 Letter Combinations of a ...
leetcode题库 LeetCode-Go 理论基础 见Note 脑图 TODO 待填充 算法题 面试高频出现,以及一些非常经典重要的算法题优先 题目列表 ...Longest Substring ...Longest ...Substring ...Palindrome Number 49.4% Easy
leetcode 2sum # Programming-Problems This will have many problems from all over the web, As of writing this readme ...Longest Substring ...Longest ...Substring ...Palindrome Number [Easy] LC11:
longest_substring mid_two_list #2021/03/30 longest_palindromic_substring reverse_a_int #2021/03/31 之字形转换 Palindrome_number #2021/04/01 myAtoi Roman_to_int #2021/04/02 regular_...
分割数组求最大差值leetcode ...Palindrome Number 56.7% 简单 10 Regular Expression Matching 25.3% 困难 11 Container With Most Water 59.3% 中等 12 Integer to Roman 61.8% 中等 13 Roman to In
3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17...
0003_Longest_Substring_Without_Repeating_Characters :star: 0004_Median_of_Two_Sorted_Arrays :star: 0005_Longest_Palindromic_Substring :star: 0006_ZigZag_Conversion 0007_Reverse_Integer 0008_String_to_...
Longest Substring Without Repeating Characters Container With Most Water Patching Array 动态规划 Triangle Maximum Subarray Maximum Product Subarray Longest Increasing Subsequence Palindrome ...