LongestPalindromicSubstring2 [source code]
public class LongestPalindromicSubstring2 {
static
/******************************************************************************/
class Solution {
public String longestPalindrome(String s) {
char[] chs = preProcess (s);
int n = chs.length;
int[] P = new int[n];
int C = 0, R = 0;
for (int i = 1; i < n - 1;i++) {
int i_mirror = 2 * C - i;
P[i] = R > i ? Math.min (P[i_mirror], R - i) : 0;
// Note: this expansion is unconditional!
while (chs[i - P[i] - 1] == chs[i + P[i] + 1])
P[i]++;
if (i + P[i] > R) {
R = i + P[i];
C = i;
}
}
int max_idx = 0, max_len = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] > max_len) {
max_len = P[i];
max_idx = i;
}
}
int max_start = max_idx - max_len;
// converting back to S_INDEX is not trivial: better remember it.
return s.substring ((max_start - 1) / 2, (max_start - 1) / 2 + max_len);
}
char[] preProcess (String s) {
int n = s.length ();
char[] chs = s.toCharArray ();
char[] res = new char[2 * n + 1 + 2];
Arrays.fill (res, '#');
res[0] = '^';
res[res.length - 1] = '$';
for (int i = 0; i < n; i++) {
res[2 * i + 2] = chs[i]; // use a case
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
LongestPalindromicSubstring2.Solution tester = new LongestPalindromicSubstring2.Solution();
String[] inputs = {
"abba", "abba",
"cbbd", "bb",
"babad", "bab",
"bb", "bb",
};
for (int i = 0; i < inputs.length / 2; i++) {
String s = inputs[2 * i], ans = inputs[2 * i + 1];
System.out.println (Printer.separator ());
String output = tester.longestPalindrome (s);
System.out.printf ("%s -> %s, expected: %s\n",
s, Printer.wrapColor (output, output.equals (ans) ? "green" : "red"), ans
);
}
}
}
所以说算法这个东西, 还是要自己思考之后才有把握, 我在自己写的过程当中, 又发现了一些之前没有发现的细节; 比如, 看我上面comment出来的地方: 为什么这个expansion是unconditional的?
事实上, 假如说我们每一个i的位置都expand, 是不是可能最后做不到2N的复杂度?
不过后来我想了一下, 还是大概理解了; 首先, 我们上面P[i]的初始值, 有两种情况, R - i或者P[mirror]. 事实上, 大部分情况下, 只有在R - i的情况下, 才会expand; 所以这个保证了我们最后还是能用aggregate的方式来得到2N的复杂度;
为什么? 你可以这样认为, 假如我们没有到R的位置, 那么我们事实上就还是在当前的最右palindrome的范围内, 那么我们的i的P肯定是跟mirror的P是一样的! 因为在同一个大的palindrome里面, 无可置疑.
那么为什么我们这里不能用一个类似if (i + P[i] == R)的condition来控制expand呢? 既然都知道了只有超过R之后才会去expand? 因为上面那句话, 有一个特例: 一开始的地方. 一开始的地方, mirror的位置(在对称轴左边, 更靠近左边)的P可能过小, 是因为左边尽头的bound的限制; 而当你到了i的对称右边的时候, 可能发现实际上是可以expand的, 这也是为什么假如P[i]即使是初始化到了R以内的地方, 也有可能最后还有继续expand (beyond P[mirror])的机会;
最后写出来了, 速度是16(88), 居然没有discussion里面之前看到的N^2方法快, 很奇怪;
这个题目最后一个难点是, 怎么从T的index转换回去S的index?
首先, 你还是一定要有一个例子:
^[#a][#b][#b][#a]#$
注意, 最后的sentinel和最后一个隔断是无所谓的; 看到这个你应该看到一个问题, 感觉T的index跟S的index好像应该有一个两倍的关系? 先别急, 仔细想想, 直接两倍对吗?
multiple of 1-based index
我们之前讨论过index的base问题, 这里有一个小的技巧要讲, 就是, 一般来说, 倍数计算, 最好是放给1based的index, 而不是0based的. 因为讲不通. 所以上面的我们其实就可以思考到:
1 + 2 * (s_index + 1) = t_index + 1
注意最左边的这个1, 是因为左边的sentinel ^.
上面得到:
2 * s_index = t_index - 2
这个是满足a在T和S里面的index的关系的: (s_index, t_index) = (0, 2).
但是我们还想满足跟a在一起的这个#: (s_index, t_index) = (0, 1).
感觉上面这个方法还是太复杂了, 你这样想, 首先, 我们先把左边这个sentinel减掉, 然后得到的就是t_index - 1, 然后我们转1based找规律:
[1 2] [3 4] [5 6] ... // t_index - 1 + 1
[1] [2] [3] ... // s_index + 1
这个规律也不难找了:
((t_index - 1 + 1) + 1) / 2 = s_index + 1
s_index = (t_index - 1) / 2
也就是我最后想要的结果了; 关键是要让上面的bracket里面的两个index都能对应到下面这个index的唯一的: [# a]都能对应到[a].
当然你也可以直接找怎么把[0 1](t_index - 1)转换成[0](s_index). 但是说实话这个规律不是那么好找;
不对啊:
[0 1] [3 4] // t_index - 1
[0] [1] // s_index
这个规律实际上不难啊, 直接就是除2啊, 因为你从上面到下面想表达的其实就是一个round down的思路而已, 那不就是除法吗?
anyway, 还是学到东西了;
Problem Description
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"
Difficulty:Medium
Total Accepted:276K
Total Submissions:1.1M
Contributor:LeetCode
Companies
microsoftamazonbloomberg
Related Topics
string
Similar Questions
Shortest PalindromePalindrome PermutationPalindrome PairsLongest Palindromic SubsequencePalindromic Substrings