Shortest Palindrome - Time Limit Exceeded


  • 1
    E
    public class Solution {
        public string ShortestPalindrome(string s) {
            bool looking = true;
            int i = 1;
            string tempS = s;
            while(looking){
                if (tempS == reverse(tempS)) looking = false;
                else {
                    tempS = (reverse(s).Substring(0,i) + s);
                    i++;
                }
            }
            
            return tempS;
        }
        
        public string reverse(string s){
            //return reversed string s
            char[] charArray = s.ToCharArray();
            Array.Reverse( charArray );
            return new string( charArray );
        }
        
    }
    

    Last executed input: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa..."

    Just started learning coding, don't know which part of my code went wrong. (or if any of it went right XD)


  • 0
    I

    could you give some comments on what you're trying to do? But for the TLE part, it seems that its because your algorithm runs in O(n^2) which does not meet the time requirements (I believe you need to beat O(n)).


  • 1
    R

    Your solution is perfectly correct. Congratulations!

    But, it is not optimized to get accepted by leetcode. I suggest you to minimize the number of operations you perform in your total code. For example,

    You are prepending a substring of the reversed string to the string itself and trying to check if it is a palindrome. So, the operations performed for each character in the string will be (in the worst case scenario),

    a. Reverse a string
    b. Cut a substring from the reversed string
    c. Add the substring and the string
    d. Reverse the bigger string
    e. compare the reversed string with the bigger string

    String operations generally are expensive. You may want to minimize by doing this.

    for each character,
    a. get the substring (i) or substring(i,s.length()-1)
    b. check if it is a palindrome.
    c. if yes, get the substring(0,i)
    c.i) reverse it
    c.ii) append it at the end of the string and return

    Also to check if a string is a palindrome, rather than reversing it and checking for string equality, just implement your own function to compare the ith and s.length()-1-i th character in the string.

    I don't guarantee you that my above suggestions will get your solution accepted. But, they will certainly make your code better.

    All the best.


Log in to reply
 

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