Using DP to memorize and DFS to get the answer but still Time Limit Exceeded! Can anybody tell me the reason?


  • 0
    X
    public class Solution {
        public List<String> wordBreak(String s, Set<String> dict) {
              	 int length=s.length();
    	        boolean[] dp=new boolean[length+1];
    	        Arrays.fill(dp, false);
    	        dp[0]=true;
    	        for(int i=1;i<=length;i++)
    	        {
    	        	for(int j=0;j<i;j++)
    	        	{
    	        		if(dp[j]&&dict.contains(s.substring(j, i)))
    	        		{
    	        			dp[i]=true;
    	        			break;
    	        		}
    	        	}
    	        }
    	        if(dp[length]==false)return new ArrayList<String>();
    	        return dfs(s,dict,dp,length);
    	 }
    	 private List<String>dfs(String s, Set<String> dict,boolean[]dp,int end)
    	 {
    		 List<String>result=new ArrayList<String>();
    		 for(int i=end;i>=0;i--)
    		 {
    			 for(int j=0;j<i;j++)
    			 {
    				 if(dp[j]&&dict.contains(s.substring(j, i)))
    				 {
    					 if(j==0)
    					 {
    						 result.add(s.substring(j,i ));
    					 }
    					 else
    					 {
    						 List<String>ans=dfs(s,dict,dp,j);
    						 for(String str:ans)
    						 {
    							 StringBuilder strbuilder=new StringBuilder(str);
    							 strbuilder.append(" ");
    							 strbuilder.append(s.substring(j,i));
    							 result.add(strbuilder.toString());
    						 }
    					 }
    				 }
    			 }
    		 }
    		 return result;
    	 }
    }

Log in to reply
 

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