Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd" Output: "bb"
Constraints:
1 <= s.length <= 1000sconsist of only digits and English letters.
A:
Use 2D array as flag
NOTE:class Solution { public: string longestPalindrome(string s) { int n = s.length(); vector<vector<bool>> V(n,vector<bool>(n,false)); int maxStart = 0, maxLen = 0; for(int len = 1;len<=n;len++){ for(int start = 0; start+len<=n;start++){ int end = start + len - 1; V[start][end] = (s[start]==s[end]) && ((start+1 > end-1) || V[start+1][end-1]); if(V[start][end]){ maxLen = len; maxStart = start; } } } return s.substr(maxStart,maxLen); } };
上面的代码，为了简洁，没有加入early stop的判断。
************* 上述代码，转成1D array ************
Tricky 的地方是： 用int类型来代表前面2次的save结果
这一次，我们保存了2条1D array. 每次，我们更改相应的 奇数/偶数条
利用了Manacher算法的思想，把输入变形了。 然后就可以用每个位置来作center， 从而不需要考虑单双。
class Solution { public: string longestPalindrome(string s) { int n = s.length(); // since every time, we shrink by width two vector<vector<bool>> V(2,vector<bool>(n,false)); int maxStart = 0, maxLen = 0; for(int len = 1;len<=n;len++){ for(int start = 0; start+len<=n;start++){ int end = start + len -1; V[len%2][start]= (s[start]==s[end]) && ( start+1 > end-1 || V[len%2][start+1]); if(V[len%2][start] && len > maxLen){ maxLen = len; maxStart = start; } } } return s.substr(maxStart,maxLen); } };
容易出错的地方还是最后的substr 的计算。 要注意，ending $ 是归属于它前一个char的。所以需要-1
class Solution { private: string modifyInput(string s){ vector<char> vec(1, '$'); for(auto ch : s){ vec.push_back(ch); vec.push_back('$'); } string res(vec.begin(), vec.end()); return res; } public: string longestPalindrome(string s) { string ms = modifyInput(s); vector<int> centers; for(int i =1; i<ms.size(); ++i){ centers.push_back(i); } int radius = 0, curMaxCenter = 1; // initially while(centers.size()){ // each time, record only the valid centers radius++; vector<int> newCenters; for(auto c : centers){ if(c-radius >=0 && c+radius < ms.size() && ms[c-radius] == ms[c+radius]){ newCenters.push_back(c); curMaxCenter = c; } } centers = newCenters; } radius--; // need -- to make is valid radius, which is on ms int start = (curMaxCenter-radius)/2; int end = (curMaxCenter +radius-1)/2;//ending $ go with char ahead，thus -1 return s.substr(start,end-start+1); } };
下面，我们用了 Manacher’s algorithm.
public class Solution {
public String longestPalindrome(String s) {
String T = preprocess(s);
int[] P = new int[T.length()];
int center = 0, right = 0;
for (int i = 1; i < T.length() - 1; i++) {
int i_mirror = 2 * center - i;
P[i] = (right - i > 0) ? Math.min(right - i, P[i_mirror]) : 0;
// Attempt to expand palindrome centered at i
while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
P[i]++;
}
// If palindrome centered at i expand past Right,
// adjust center based on expanded palindrome.
if (i + P[i] > right) {
center = i;
right = i + P[i];
}
}
// Find the maximum element in P.
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < T.length() - 1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
int startPos = (centerIndex - 1 - maxLen) / 2;
return s.substring(startPos, startPos+ maxLen); }
private String preprocess(String s) {
// Add # before and after each character
// ^ and $ signs are sentinels appended to each end to avoid bounds
// checking
StringBuffer buf = new StringBuffer();
if (s.length() == 0)
return "^$";
buf.append("^");
for (int i = 0; i < s.length(); i++) {
buf.append("#" + s.charAt(i));
}
buf.append("#&");
return buf.toString();
}
}
Mistakes:
1: for loop 计算P的时候，由于我们首尾加了^ $， 因此是从1 到 T.length() -2的。
2：当buf.append('#'+s.charAt(i)）是不对的。因为char+char的结果还是一个char类型。 应该是"#"
3: 第二遍， 当做for循环 来计算P[i] 的时候，要从i = 1 的地方计算，因为第一个位置，已经默认为0 了。 而且， 包括i < n -1 ， 也是避免了最后一个位置的计算。 （避免了处理边界问题）
for(int i =1;i<n -1 ;i++){ // n-1 ,avoid the last case ， as wel as the first position
Learned:
Manacher’s algorithm.
这是leetcode的链接。Here, we discuss an algorithm that runs in O(N) time and O(N) space, also known as Manacher’s algorithm.
Hint:
Think how you would improve over the simpler O(N2) approach. Consider the worst case scenarios. The worst case scenarios are the inputs with multiple palindromes overlapping each other. For example, the inputs: “aaaaaaaaa” and “cabcbabcbabcba”. In fact, we could take advantage of the palindrome’s symmetric property and avoid some of the unnecessary computations.
An O(N) Solution (Manacher’s Algorithm):
First, we transform the input string, S, to another string T by inserting a special character ‘#’ in between letters. The reason for doing so will be immediately clear to you soon.
For example: S = “abaaba”, T = “#a#b#a#a#b#a#”.
To find the longest palindromic substring, we need to expand around each Ti such that Ti-d … Ti+d forms a palindrome. You should immediately see that d is the length of the palindrome itself centered at Ti.
We store intermediate result in an array P, where P[ i ] equals to the length of the palindrome centers at Ti. The longest palindromic substring would then be the maximum element in P.
Using the above example, we populate P as below (from left to right):
T = # a # b # a # a # b # a # P = 0 1 0 3 0 1 6 1 0 3 0 1 0Looking at P, we immediately see that the longest palindrome is “abaaba”, as indicated by P6 = 6.
Did you notice by inserting special characters (#) in between letters, both palindromes of odd and even lengths are handled graciously? (Please note: This is to demonstrate the idea more easily and is not necessarily needed to code the algorithm.)
Now, imagine that you draw an imaginary vertical line at the center of the palindrome “abaaba”. Did you notice the numbers in P are symmetric around this center? That’s not only it, try another palindrome “aba”, the numbers also reflect similar symmetric property. Is this a coincidence? The answer is yes and no. This is only true subjected to a condition, but anyway, we have great progress, since we can eliminate recomputing part of P[ i ]‘s.
Let us move on to a slightly more sophisticated example with more some overlapping palindromes, where S = “babcbabcbaccba”.
Above image shows T transformed from S = “babcbabcbaccba”. Assumed that you reached a state where table P is partially completed. The solid vertical line indicates the center (C) of the palindrome “abcbabcba”. The two dotted vertical line indicate its left (L) and right (R) edges respectively. You are at index i and its mirrored index around C is i’. How would you calculate P[ i ] efficiently?
The two green solid lines above indicate the covered region by the two palindromes centered at i and i’. We look at the mirrored index of i around C, which is index i’. P[ i' ] = P[ 9 ] = 1. It is clear that P[ i ] must also be 1, due to the symmetric property of a palindrome around its center.
Now we are at index i = 15, and its mirrored index around C is i’ = 7. Is P[ 15 ] = P[ 7 ] = 7?
Colored lines are overlaid around the center at index i and i’. Solid green lines show the region that must match for both sides due to symmetric property around C. Solid red lines show the region that might not match for both sides. Dotted green lines show the region that crosses over the center.
Let’s summarize the key part of this algorithm as below:
if P[ i' ] ≤ R – i,
then P[ i ] ← P[ i' ]
else // P[i'] > R–i ----------->
P[ i ] ≥ R . (Which we have to expand past the right edge (R) to find P[ i ].
See
how elegant it is? If you are able to grasp the above summary fully,
you already obtained the essence of this algorithm, which is also the
hardest part.then P[ i ] ← P[ i' ]
else // P[i'] > R–i ----------->
P[ i ] ≥ R . (Which we have to expand past the right edge (R) to find P[ i ].
The final part is to determine when should we move the position of C together with R to the right, which is easy:
If the palindrome centered at i does expand past R, we update C to i,
(the center of this new palindrome), and extend R to the new
palindrome’s right edge.
In each step, there are two
possibilities. If P[ i' ] ≤ R – i, we set P[ i ] to P[ i' ] which takes
exactly one step. Otherwise we attempt to change the palindrome’s center
to i by expanding it starting at the right edge, R. Extending R (the
inner while loop) takes at most a total of N steps, and positioning and
testing each centers take a total of N steps too. Therefore, this
algorithm guarantees to finish in at most 2*N steps, giving a linear
time solution.Note:
This algorithm is definitely non-trivial and you won’t be expected to come up with such algorithm during an interview setting. However, I do hope that you enjoy reading this article and hopefully it helps you in understanding this interesting algorithm. You deserve a pat if you have gone this far!
Further Thoughts:
- In fact, there exists a sixth solution to this problem — Using suffix trees. However, it is not as efficient as this one (run time O(N log N) and more overhead for building suffix trees) and is more complicated to implement. If you are interested, read Wikipedia’s article about Longest Palindromic Substring.
- What if you are required to find the longest palindromic subsequence? (Do you know the difference between substring and subsequence?)
» Manacher’s Algorithm O(N) 时间求字符串的最长回文子串 (Best explanation if you can read Chinese)
» A simple linear time algorithm for finding longest palindrome sub-string
» Finding Palindromes
» Finding the Longest Palindromic Substring in Linear Time
» Wikipedia: Longest Palindromic Substring
----------------自己第一遍的解法----------------------------
思想是：每次加入一个char ch，然后，看前一个位置的所有的match 的点，如果加上ch之后，还能组成palindrome，就把该位置，加入list中。
复杂度，最差的情况是O(n^2)
public class Solution {
public String longestPalindrome(String s) {
// adding char in the list
if (s == null || s.length() <= 1)
return s;
int n = s.length();
// for each newly added char, remember all the previous matching
// positions,
// that would make it palindrome
ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
ArrayList<Integer> al = new ArrayList<Integer>();
// remember its selft matching
al.add(i); // adding its selft
if (i > 0) { // test i and i-1
if (ch == s.charAt(i - 1)) // things like: s = "abb", and i = 2
al.add(i - 1);
// test all the matching positions in the preList
ArrayList<Integer> preAl = all.get(i - 1);
for (Integer k : preAl)
if (k > 0)
if (s.charAt(k - 1) == ch)
al.add(k - 1);
}
all.add(al);
}
// calculate the max position
int maxBegin = 0, maxEnd = 1;
for (int i = 0; i < n; i++) {
ArrayList<Integer> al = all.get(i);
for (int j = 0; j < al.size(); j++) {
if (maxEnd - maxBegin < i - al.get(j)) {
maxBegin = al.get(j);
maxEnd = i;
}
}
}
return s.substring(maxBegin, maxEnd + 1);
}
}
No comments:
Post a Comment