public class Solution {
public String shortestPalindrome(String s) {
if(isPalindrome(s))return s;
int i=s.length();
while(i>0){
String sub1 = s.substring(0,i);
if(isPalindrome(sub1))break;
}
i++;
String sub2 = s.substring(i);
StringBuilder sb = new StringBuilder();
for(int j=sub2.length()1;j>=0;j){
sb.append(sub2.charAt(j));
}
for(int j=0;j<s.length();j++){
sb.append(s.charAt(j));
}
return sb.toString();
}
private boolean isPalindrome(String s){
int i=0,j=s.length()1;
while(i<j){
if(s.charAt(i++)!=s.charAt(j))return false;
}
return true;
}
}
My Java Solution O(N^2), do not need to use Manacher’s Algorithm


I believe this is O(N^2) (each isPalindrome is O(N), done N times). I wrote equivalent code in C++, had it fail due to time limit exceeded, think you must have just slipped under max time due to implementation.
If interested, I doctored my code so it was still O(N^2) but could handle the large case with smaller constant out front and therefore pass. (https://leetcode.com/discuss/36868/c4mscheatcouldinspirebetteralgorithm). Curious if simple nonManachers O(N) exists, but doubtful much simpler.