1. 题目描述
2. Solution 1: [TLE] Brute force
1、思路
两层循环遍历所有子串，判断是否为回文，保留最长的子串。
2、代码实现
/*
Solution 1: Brute force
两层循环遍历所有子串，判断是否为回文，保留最长的子串。
*/
public class Solution1 {
public String longestPalindrome(String s) {
String result = "";
int maxLen = 0;
int n = s.length();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
String cur = s.substring(i, j); // s[i, j), 故上面的j要取到等号
if (isPalindromic(cur) && cur.length() > maxLen) {
result = cur;
maxLen = Math.max(maxLen, result.length());
}
}
}
return result;
}
private boolean isPalindromic(String s) {
int n = s.length();
for (int start = 0, end = n - 1; start < end; start++, end--)
if (s.charAt(start) != s.charAt(end)) return false;
return true;
}
}
time complexity: 两层循环O(n2)，判断是否回文O(n)，综合为O(n3)
space complexity: O(1)
提交之后，TLE(Time Limit Exceeded)
3. Solution 2: LCS
3.1 子问题：最长公共子串(Longest Common Substring)
首先，引入问题最长公共子串(Longest Common Substring)，原题见 NC127
1、分析: DP
1) 状态定义
dp[i][j] 表示字符串s1中第i个字符和s2中第j个字符所构成的最长公共子串。
2) 初始状态
dp\[i][j] = {0}
3) 状态转移方程
dp\[i][j] = 0, if s1[i] != s2[j]
dp\[i][j] = dp\[i-1][j-1] + 1, if s1[i] == s2[j]
状态转移方程中出现了 i - 1，要求必须 i>=1，遍历字符串的时候，i从0开始。
故，对上面的公式做个替换 i -> i + 1，导出
dp\[i+1][j+1] = dp\[i][j] + 1, if s1[i] == s2[j]
****
2、示例
String s1 = "1AB2345CD", s2 = "12345EF", expected = "2345";
手动模拟结果:
3、代码实现
/*
DP
1) 状态定义
dp[i][j] 表示字符串s1中第i个字符和s2中第j个字符所构成的最长公共子串。
2) 初始状态
dp[i][j] = {0}
3) 状态转移方程
dp[i][j] = 0, if s1[i] != s2[j]
dp[i][j] = dp[i-1][j-1] + 1, if s1[i] == s2[j]
*/
public class Solution {
@Test
public void test1() {
String s1 = "1AB2345CD", s2 = "12345EF", expected = "2345";
assertEquals(expected, LCS(s1, s2));
}
/**
* longest common substring
*
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS(String s1, String s2) {
// write code here
int maxLen = 0;
int end = 0;
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (s1.charAt(i) == s2.charAt(j)) {
dp[i + 1][j + 1] = dp[i][j] + 1;
if (dp[i + 1][j + 1] > maxLen) {
maxLen = dp[i + 1][j + 1];
end = i;
}
}
}
}
return s1.substring(end - maxLen + 1, end + 1);
}
}
time complexity: 两层循环，O(n^2)
space complexity: 二维数组，O(n^2)
4、优化，DP使用一维数组
/*
DP使用一维数组
*/
public class Solution1 {
public String LCS(String s1, String s2) {
int maxLen = 0;
int end = 0;
int m = s1.length(), n = s2.length();
int[] dp = new int[n + 1];
for (int i = 0; i < m; i++) {
for (int j = n - 1; j >= 0; j--) {
if (s1.charAt(i) == s2.charAt(j)) {
dp[j + 1] = dp[j] + 1;
if (dp[j + 1] > maxLen) {
maxLen = dp[j + 1];
end = i;
}
} else dp[j + 1] = 0;
}
}
return s1.substring(end - maxLen + 1, end + 1);
}
}
time complexity: 两层循环，O(n^2)
space complexity: 一维数组，O(n )
3.2 用LCS解决当前问题
1、思路
根据回文的定义，正序读与倒序读一样。故，把输入字符串s做逆置为 rev，求LCS(s, rev)。
例1:
String s = "caba";
String rev = new StringBuilder(s).reverse().toString(); // "abac"
LCS(s, rev) = "aba";
例2:
String s = "abc435cba";
String rev = "abc534cba";
LCS(s, rev) = "abc" || "cba";
显然这两个字符串都不是回文串，所以求出最长公共子串后，并不一定是回文串，还需要判断该字符串倒置前的下标和当前的字符串下标是不是一致。
具体地，正确示例
a) dp过程
b) 判断下标一致
在dp[3][4] = 3时，取得最长公共子串
此时，j = 2, rev[j] = 'a'，为倒着读终点。
由j推导出顺着读的起点为: idxInSource = n - 1 - j = 4 - 1- 2 = 1。
由dp推导出的顺着读终点，idxInSource + dp[3][4] - 1 = 1 + 3 - 1 = 3。
实际顺着读终点为 i = 3。
综上，满足要求。
错误示例
a) dp过程
b) 判断下标一致
2、代码实现
public class Solution2 {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) return s;
String rev = new StringBuilder(s).reverse().toString();
int n = s.length();
int[] dp = new int[n + 1];
int maxLen = 0;
int end = 0;
for (int i = 0; i < n; i++) {
for (int j = n - 1; j >= 0; j--) {
if (s.charAt(i) == rev.charAt(j)) {
dp[j + 1] = dp[j] + 1;
if (dp[j + 1] > maxLen) {
int idxInSource = n - 1 - j; // dp推导出的顺读起点
// dp导出的顺读终点 实际顺读终点
if (idxInSource + dp[j + 1] - 1 == i) {
maxLen = dp[j + 1];
end = i;
}
}
} else dp[j + 1] = 0;
}
}
return s.substring(end - maxLen + 1, end + 1);
}
}
time complexity: O(n^2)
space complexity: O(n)
4. Solution 3
1、思路： 用DP优化暴力法
Dynamic Programming
- 状态定义
boolean dp[i][j] = s[i, j] is Palindromic - 状态初始条件
dp[i][j] = true if len(s[i, j]) == 1 or j == i or j - i == 0;
dp[i][j] = s[i] == s[j] if len(s[i, j]) == 2 or j == (i + 1) or j - i == 1; - 状态转移方程
dp[i][j] = s[i] == s[j] && dp[i+1][j-1]
判断条件整合：
a. 若: j - i == 0 , 则dp[i][j] = (s[i] == s[j]) 恒为true, 1个字符自然回文
b. 若: j - i == 1 , 则dp[i][j] = s[i] == s[j] 2个字符，首尾相等即可
c. 若: j - i == 2 , 则dp[i][j] = s[i] == s[j] 3个字符，首尾相等即可，中间有1个字符，不打紧
d. 若: j - i > 2 , 则dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1] 4个字符(含)，首尾相等，外加中间子串为回文才行
a. b. c. 判断条件整合 => s[i] == s[j] && (j - i <= 2)
与d. 合并后 判断条件整合为一个 => s[i] == s[j] && ( (j - i <= 2) || dp[i + 1][j - 1] )
2、示例
input: s = "babad";
用j遍历行，i遍历列，只使用了下三角
3、代码实现
public class Solution3 {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) return s;
String res = "";
boolean[][] dp = new boolean[s.length()][s.length()];
int max = 0;
for (int j = 0; j < s.length(); j++) {
for (int i = 0; i <= j; i++) {
dp[i][j] = s.charAt(i) == s.charAt(j) &&
((j - i <= 2) || dp[i + 1][j - 1]);
if (dp[i][j] && (j - i + 1 > max)) {
max = j - i + 1;
res = s.substring(i, j + 1); // [i, j+1)
}
} // end of inner for loop
} // end of outer for loop
return res;
}
}
time: O(n^2)
space: O(n^2)
4、优化使用一维数组
/*
对Solution3的优化，使用一维数组
*/
public class Solution4 {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) return s;
String res = "";
boolean[] dp = new boolean[s.length()];
int n = s.length();
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= i; j--) {
dp[j] = s.charAt(i) == s.charAt(j) &&
((j - i) < 3 || dp[j - 1]);
if (dp[j] && j - i + 1 > res.length())
res = s.substring(i, j + 1); // [i, j+1)
}
}
return res;
}
}
time: O(n^2)
space: O(n)
5. Solution 4
1、思路：中心扩展
回文一定是对称的，所以可以循环选择一个中心，进行左右扩展，判断左右字符是否相等。
因为字符串长度可能为奇数，也可能是偶数，所以中心可以是字符，也可以是两个字符间隙。
设字符串长度为n，则间隙为n-1，可能的中心有 n+(n-1) = 2n - 1个。
2、代码实现
public class Solution5 {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) return null;
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int n = Math.max(expandAroundCenter(s, i, i), // 以i为中心扩展
expandAroundCenter(s, i, i + 1)); // 以i后面的间隔为中心扩展
if (n > end - start) {
start = i - (n - 1) / 2;
end = i + n / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
int l = left, r = right;
while (l >= 0 && r < s.length() &&
s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
return r - l - 1;
}
}
time complexity: O(n^2)
space complexity: O(1)
6. Solution 5: Manacher's Algorithm 马拉车算法
马拉车算法 Manacher‘s Algorithm 是用来查找一个字符串的最长回文子串的线性方法，由一个叫Manacher的人在1975年发明的，这个方法的最大贡献是在于将时间复杂度提升到了线性。
1、思路分析
- Step 1: 预处理
由于回文分为偶回文(如，bccb)和奇回文(如，bcacb)，而在处理奇偶问题上会比较繁琐，这里使用一个技巧
a.) 在字符串首尾及每个字符间都插入一个"#"，这样可以使得原先的奇偶回文都变为奇回文；
b.) 接着在首尾两端各插入"$"和"^"，这样中心扩展寻找回文的时候会自动退出循环，不需要每次判断是否越界；
T: 处理后的数组，P: 从中心扩展的长度
首先，用一个数组P保存从重心扩展的字符串最多个数，而它刚好也是去掉"#"的原字符串的总长度。如，index=6的地方，P[6]=5，所以它是从左边扩展5个字符，相应的右边也是扩展5个字符，也就是"#c#b#c#b#c#"。而去掉#恢复到原来的字符串，变成"cbcbc"，它的长度刚好也就是5。
- Step 2: 求原始字符串下标
用P的下标i减去P[i]，再除以2，就是原字符串的开头下标了。
如，P[6] = 5，也就是回文串的最大长度是5，对应的下标是6，所以原字符串的开头下标是(6-5) / 2 = 0。所以，只需要返回原字符串的第0到第(5-1)位就可以了。
Step 3: 求每个P[i]
用C表示回文串的中心，用R表示回文串的右边半径，所以R=C+P[C]。C和R所对应的回文串是当前循环中R最靠右的回文串。
考虑求P[i]，用i_m表示当前需要求的第i个字符关于C对应的下标。
现在要求P[i]，如果是用中心扩展法，那就向两边扩展比对就行了。其实可以利用回文串C的对称性。i关于C的对称点是i_m，P[i_m]=3，所以P[i] 也等于 3。
但是有三种情况将会造成直接赋值为P[i_m]是不正确的，下边一一讨论。
case 1: 超出了R
当要求P[i]的时候，P[i_m]=7，而此时P[i]并不等于7，为什么呢？因为我们从i开始往后数7个，等于22，已经超过了最右的R，此时不能利用对称性了，但我们一定可以扩展到R的，所以P[i]至少等于R-i=20-15=5，会不会更大呢，我们只需要比较T[R+1]和T[R+1]关于i的对称点就行了，就像中心扩展法一样一个个扩展。
case 2: P[i_m]遇到了原字符串的左边界
此时P[i_m]=1，但是P[i]赋值成1是不正确的，出现这种情况的原因是P[i_m]在扩展的时候首先是"#"=="#"，之后遇到了"^"和另一个字符比较，一就是到了边界，才终止循环的。而P[i]并没有遇到边界，所以我们可以通过中心扩展法一步一步向两边扩展就行了。
case 3: i等于R
此时，先把P[i]赋值为0，然后通过中心扩展法一步一步扩展。
- Step 3: 考虑C和R的更新
就这样一步一步的求出每个P[i]，当求出的P[i]的右边界大于当前的R时，就需要更新C和R为当前的回文串了。因为必须保证i在R里面，所以一旦有更右边界的R就要更新R。
此时的P[i]求出了将会是3，P[i]对应的右边界将是10+3=13，所以大于当前的R，需要把C更新成i的值，也就是10，R更新成13。
2、代码实现
package Q0099.Q0005LongestPalindromicSubstring;
public class Solution6 {
public String preProcess(String s) {
int n = s.length();
if (n == 0) return "^$";
StringBuilder ret = new StringBuilder("^");
for (int i = 0; i < n; i++)
ret.append("#").append(s.charAt(i));
ret.append("#$");
return ret.toString();
}
public String longestPalindrome(String s) {
String T = preProcess(s);
int n = T.length();
int[] P = new int[n];
int C = 0, R = 0;
for (int i = 1; i < n - 1; i++) {
int i_m = 2 * C - i;
if (R > i) {
P[i] = Math.min(R - i, P[i_m]);
} else {
P[i] = 0; // 等于R的情况
}
// 碰到之前的三种情况，需要利用中心扩展法
while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i]))
P[i]++;
// 判断是否需要更新R
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// 找出P的最大值
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
int start = (centerIndex - maxLen) / 2; // 最开始讲的求原字符串下标
return s.substring(start, start + maxLen);
}
}