# C++ 4 ms (O(n) time & O(n) memory) ,NOT using KMP. Just one pass.

• This code using a array palinIndex[i] to memory the longest palindrome string ended with i:
palinIndex[i] indicates string ended with s[i] and started with s[palinIndex[i]] is a palindrome, that is,
{palinIndex[i],...,i }construct a longest palindrome string.
How to caculate palinIndex:

1. just i, s[i] is a palindrome string,so palinIndex[i] = i;

2. s[i-1]s[i] is palindrome ,so palinIndex[i] = i-1;

1. s[i-2]s[i-2]s[i] is palindrome ,so palinIndex[i] = i - 2;
1. {palinIndex[i-1],...i-1} is palindrome, so if s[palindrome[i-1] -1] == s[i], palinIndex[i] = palinIndex[i]-1;
1. specially, for example "aaabcaaa". if palinIndex[i-1] == palinIndex[i-2], that is say {palinIndex[i-1],...,i-1} is same! so palinIndex[i] = palinIndex[i-1],if s[i] == s[palinIndex[i-1]];

All test case is passed! IS THIS RIGHT? I don't konw ,may I miss some case!

``````class Solution {
public:
string shortestPalindrome(string s) {
string str = "";
if(s.size() == 0)return str;
int palinIndex[s.size()];
int maxIndex = 0;
palinIndex[0] = 0;
for(int i = 1; i < s.size();i++){

int index = i;
if(i-1 >= 0 && s[i] == s[i-1]){
index = i - 1;
}
if(i-2 >= 0 && s[i] == s[i-2]){
index = i - 2;
}
if(palinIndex[i-1]-1 >= 0 && s[i] == s[palinIndex[i-1] - 1]){
index = min(index,palinIndex[i-1] - 1);
}
if(i > 2 && palinIndex[i-1] == palinIndex[i-2]){
if(s[i] == s[palinIndex[i-1]]){
index = min(index,palinIndex[i-1]);
}
}
palinIndex[i] = index;
if(index == 0){
maxIndex = i;
}
}
str = s.substr(maxIndex+1,s.size() - maxIndex);
reverse(str.begin(),str.end());
return str + s;
}
``````

};

• Hello,The thoughts of your code is inspiring,but I think there might be some problem,for example when s[i]!=s[palinIndex[i-1]-1],and,palinIndex[i-1]!=palinIndex[i-2],your solutions just make palinIndex[i]=i-1||i-2,
but it may be any number between palinIndex[i-1] to i,take this string an example:
"dcbccccbccccbcd",it self is palindromic but throught this solution the result is "dcbccccbccccbcdcbccccbccccbcd"

• Thanks a lot :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.