Have you encountered the time limit exceeded error using stacks?


  • 0
    M

    I am using stacks in Java and works out fine on the EXTREMELY long input on my PC, yet it shows time limit exceeded on the server, anybody can explain this to me?

    my code:

    public static String reverseWords(String s) {
       Stack<Character> charStack=new Stack<Character>();
       //System.out.println(charStack.capacity());
       if(s.equals(null))
    	   return s;
       int i=0;
       String newString= new String();
       while(i!=s.length())
       {
    	   charStack.push(s.charAt(i));
    	   //System.out.println(charStack.peek());
    	   if(charStack.peek()==' ')
    	   {
    		   if(newString.equals(null))
    			   charStack.pop();
    		   while(charStack.size()!=0)
    		   {
    			   newString =charStack.pop()+ newString ;
    		   }
    	   }
    	   i++;
       }
       newString = ' '+newString;
       while(charStack.size()!=0)
       {
    	   newString =charStack.pop()+ newString ;
       }
       
       return newString;
    }
    

    and the test case, like I said it is EXTREMELY LOOOOOOOOONG: I cannot write it down in a reply, but you are welcomed to use my code in the submission, and you will see the failing test case


  • 0
    S

    Please show your code and the test case it fails on.


  • 0
    M

    I cannot write the test case for you because it is TOO LONG, but you are welcome to use my code to submit and you will see that case


  • 0
    M

    TLE doesn't only mean that you have an infinite loop in your code. It also means that your code takes far longer than it needs to in order to solve the problem. Your algorithm uses string concatenation to regenerate the words in the right order, and the way you do it creates a string for every character. According to stackoverflow,

    newString= b + newString;
    

    is

    newString = new StringBuilder().append(b).append(newString).toString();
    

    and you are doing that for every non-whitespace character.

    Since your current code creates a new string for each character, you will end up spending a lot of time creating strings that get used once then discarded in the next loop. Why not just use an int stack and store the start and end of words, taking a substring once you find the bounds, and making the string that way? It removes a large number of the string creations, which should speed up your solution enough to avoid the TLE.


  • 0
    M

    I see, I am using String builder right now to improve the increment of the string


Log in to reply
 

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