Can't figure out why dp TLE, Please help me


  • 0
    B
     public List<String> wordBreak(String s, Set<String> wordDict) {
        int n = s.length();
        if(n == 0)  return new ArrayList<String>();
        List<String>[] dp = new ArrayList[n+1];
        for(int i = 0; i <= n; i++)
            dp[i] =new ArrayList<String>();
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < i; j++)
                if(wordDict.contains(s.substring(j,i))){
                    if(j == 0) dp[i].add(s.substring(j,i));
                    else if(dp[j].size()!=0){
                        for(int k = 0; k < dp[j].size(); k++){
                            String str = dp[j].get(k);
                            str += ' '+s.substring(j,i);
                            dp[i].add(str);
                        }
                    }
                }
        }
        return dp[n];
    }

Log in to reply
 

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