I got Time Limit Exceeded problem

  • 0
        String result="";
    	List<String> words = new ArrayList<String>();
    	Pattern p = Pattern.compile("\\w+");
    	Matcher m = p.matcher(s);
    	for(int i=words.size()-1;i>=0;i--)
    		result+=words.get(i)+" ";

    I use the regex to analyse the String s and I run well in my laptop, but got time limit exceeded, cloud anyone tell me where the problem is ?thanks :)
    PS. I have imported the package in the code

  • 0

    What I think is that most probably your last loop is taking a lot of time. Addition of new elements to a String is O(n^2) which will give TLE for large value of n. Hence try using StringBuilder instead. Append the words in a String Builder and then convert it to String and return the answer.
    Here is the time difference in using StringBuilder and String to get a large string:

    public class pract {

    public static void main(String args[])
    	long st = System.currentTimeMillis();
    	String s="";
    	for (int i=1;i<=100000;i++)
    	long end= System.currentTimeMillis();
    	st = System.currentTimeMillis();
    	StringBuilder  sb =new StringBuilder("");
    	for (int i=1;i<=100000;i++)
    	String s1= sb.toString();
    	 end= System.currentTimeMillis();


    the out put of the above code is the following


  • 0

    Since there is no limit on using extra space, I believe split() and trim() functions are the tools to do the job. No need of nested loop.

    public String reverseWords(String s)
    	String []terms = s.split(" ");
    	String s1 = "";
    	for (int i=terms.length-1; i>=0; i--)
    		if (terms[i].length() >0 && !terms[i].equals(" "))
    			s1 = s1 + terms[i] + " ";
    	return s1.trim();

Log in to reply

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