Any Idea to optimize?


  • 0
    Y

    Hi: any idea to optimize? My code has a time limit exceed error.

          public ArrayList<String> wordBreak(String s, Set<String> dict) {
                   
                       ArrayList<String>result=new ArrayList<String>();
            	       if(s.length()==0){
            	    	   result.add("");
            	           return result;
            	       }
            	       for(String i : dict){
            	           if(s.indexOf(i,0)==0){// if s starts with the string i
            	               ArrayList<String>more=wordBreak(s.substring(i.length()),dict);// recurse
            	               if(more.size()>0){
            	                    for(String str : more){
            	                        String temp=i+" "+str;
            	                        result.add(temp);
            	                 }
            	               }
            	           }
            	       }
            	       return result;
                    
            }

  • 0
    S

    Could you please detail your question? Is the solution accepted that you are asking for a better solution, or it fails in test cases? No matter what situation you are in, please update your post with algorithm explanation and comments in code. Thanks.


  • 0
    Y

    Actually, I figured out a way. I used a cache and changed the loop in my original code.


  • 0
    K

    There are several parts can be optimized:

    (1) use dynamic programming to get the all possible splitting.
    (2) use position rather than string in dynamic programming in order to save memory.


Log in to reply
 

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