Plese help: I use Hashmap to store the results. Why it is still TLE?


  • 0
    G

    I used DFS recursion and Hashmap to store the results. Why it is still TLE? Anybody tells me the reason? Thank you very much!

    Map<String,List<String>> map=new HashMap<>();
    public static List<String> wordBreak(String s, Set<String> wordDict) {
    	        List<String> res= new ArrayList<>();        
    	        String f=new String();
    	        help(s,res,wordDict,f);
    	        return res;
    	    }
    public void help(String s, List<String> res, Set<String> dict, String f){
    	        if(map.get(s)!=null){
    	                res=map.get(s);
    	        }
                String save=f;
    	        if(s.length()==0){
    	            res.add(new String(f.trim()));
    	            map.put(s,res);
    	            return;
    	        }
    	        for(int i=1;i<=s.length();i++){
    	            String sub=s.substring(0,i);
    	            if(!dict.contains(sub)) continue;
    	            else{
    	                f=f+sub+" ";
    	                help(s.substring(i),res,dict,f);
    	                f=save;  
    	            }   	           
    	        }    
    	    }

Log in to reply
 

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