Help!! get TLE in case aaaaaaaa.....b is there any wrong with my solution?


  • 0
    M
    boolean[] dp;
    public List<String> wordBreak(String s, Set<String> wordDict) {
        dp = new boolean[s.length()+1];
        dp[0] =true;
        List<String> res = new LinkedList<>();
        getBreaks(s,0,wordDict,res);
        return res;
       
    }
    
    private void getBreaks(String s,int start,Set<String> wordDict,List<String> res){
        if(start==s.length()){
            if(dp[s.length()]){
                StringBuilder sb = new StringBuilder();
                int j=0;
                for(int i=1;i<=s.length();i++){
                    if(dp[i]){
                        sb.append(s.substring(j,i));
                        j=i;
                    }
                }
                res.add(sb.toString());
            }
            return;
        }
        for(int i=1;i+start<=s.length();i++){
            if(dp[start]==true){
                String sub = s.substring(start,i+start);
                if(wordDict.contains(sub)){
                    dp[i+start] = true;
                    getBreaks(s,i+start,wordDict,res);
                    dp[i+start] = false;
                }
            }else{
                break;
            }
        }
    }

Log in to reply
 

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