My Java Solution O(N^2), do not need to use Manacher’s Algorithm


  • 0
    W
    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;
        }
    }

  • 2
    O

    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/c-4ms-cheat-could-inspire-better-algorithm). Curious if simple non-Manachers O(N) exists, but doubtful much simpler.


  • 0
    W

    Thank you very much....forgot to consider isPalindrome......


  • 0
    F

    dude. i ran your solution and i got LTE...


  • 0
    J

    yeah, me too...


  • 0
    R

    can't believe this could be accepted.


  • 0
    Z

    You can just sb.append(s) -- no need another for loop.


Log in to reply
 

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