I got Time Limit Exceeded problem


  • 0
    C
        String result="";
    	List<String> words = new ArrayList<String>();
    	Pattern p = Pattern.compile("\\w+");
    	Matcher m = p.matcher(s);
    	while(m.find())
    		words.add(m.group());
    	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
    P

    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++)
    		s+=i;
    	long end= System.currentTimeMillis();
    	System.out.println(end-st);
    	st = System.currentTimeMillis();
    	StringBuilder  sb =new StringBuilder("");
    	for (int i=1;i<=100000;i++)
    		sb.append(i);
    	String s1= sb.toString();
    	 end= System.currentTimeMillis();
    	System.out.println(end-st);
    }
    

    }

    the out put of the above code is the following

    26441
    6


  • 0
    F

    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.