My concise answer.


  • 32
    M
    public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> result = new ArrayList<String>();
        for(int j = s.length() - 1; j >= 0; j--){
            if(dict.contains(s.substring(j)))
                break;
            else{
                if(j == 0)
                    return result;
            }
        }
        for(int i = 0; i < s.length()-1; i++)
        {
            if(dict.contains(s.substring(0,i+1)))
            {
                List<String> strs = wordBreak(s.substring(i+1,s.length()),dict);
                if(strs.size() != 0)
                    for(Iterator<String> it = strs.iterator();it.hasNext();)
                    {
                        result.add(s.substring(0,i+1)+" "+it.next());
                    }
            }
        }
        if(dict.contains(s)) result.add(s);
        return result;
    }
    

    }


  • 0
    This post is deleted!

  • 0
    K

    Is this solution considered "dynamic programming"?


  • 0
    Z

    Seems that we have to check the false situation first.


  • 0
    H

    Yes it is, as he only computes suffixes once, it is a pretty clever implementation.


  • 0
    S

    Seems to me it will compute suffixes over and over


  • 9
    M

    The first for loop for checking is the key to reduce run time. Without it, it will
    result in TLE. I re-write it to C++ code and get 4ms AC. Thanks !!

    I also try to add hash to speed up. However, the run time is still the same.

        class Solution {
        public:
            // the run time is still 4ms even with hash 
            unordered_map<string , vector<string>> dpHash;
            
            // it runs 4ms. the key factor it that it checks from both side to filter 
            // out impossible combination in every early stage
            vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
                vector<string> res; 
                // check hash first 
                if (dpHash.find(s) != dpHash.end()) {
                    return dpHash[s];
                }
                
                // check if need go further
                // it there's no checking here, the run time will be 
                // wi hash : 20ms
                // wo hash : TLE
                bool notFound = true;
                for (int i = s.size() - 1; i >=0; --i) {   // key here
                    if (wordDict.find(s.substr(i)) != wordDict.end()) {
                        notFound = false;
                        break;
                    } 
                }
                if (notFound) { return res; }
                
                // go further 
                if (wordDict.find(s) != wordDict.end()) { res.push_back(s); }
                for (int i = s.size() - 2; i >= 0; --i) {
                    if (wordDict.find(s.substr(0, i + 1)) != wordDict.end()) {
                        vector<string> subRes = wordBreak(s.substr(i + 1), wordDict);
                        for (auto tmp : subRes) {
                            res.push_back(s.substr(0, i + 1) + " " + tmp);
                        }
                    } 
                }
                
                dpHash[s] = res;  // update hash
                return res;
            }
    };

  • 0
    F

    I thinks its not the dp solution


  • 0
    S

    What's the time complexity of this? Thanks


  • 0
    J

    This is search...not dp...
    There would be some redundant recursive loops in this way.


  • 7
    K

    This is my DP solution:

    public class Solution {
        public List<String> wordBreak(String s, Set<String> wordDict) {
            LinkedList<String>[] dp = (LinkedList<String>[]) new LinkedList<?>[s.length()+1];
            for(int i = s.length()-1; i >= 0; i--){
                if(wordDict.contains(s.substring(i,s.length()))) break;
                if(i == 0) return new LinkedList<String>();
            }
            
            for(int i = 0; i < dp.length; i++) dp[i] = new LinkedList<String>();
           
            for(int i = 1; i <= s.length(); i++) {
                for(int j = 0; j < i; j++) {
                    if((j == 0 || dp[j].size() > 0) && wordDict.contains(s.substring(j,i))) {
                        if(j == 0) dp[i].add(s.substring(j,i));
                        else {
                            for(String c : dp[j]) {
                                dp[i].add(c + " " + s.substring(j,i));
                            }
                        }
                    } 
                }
            }
            return dp[s.length()];
        }
    }

  • 0

    Could anybody please explain why would the first for loop works if the test case is 'aaaaa...aaaa', ['a', 'aa', 'aaa', ... 'aaa...aa']? Thanks!


  • 0
    K

    @hirdyesh No, this is not a DP solution, it is a simple recursive search solution (backtracking), I wonder why it got so many upvotes.


  • 0
    F

    This is fast b/c the first for loop terminates in O(n) if the last char in the string is not achievable. If you start by using the dp solution similar to wordBreakI, then it takes O(n^2), which makes the tests 10ms longer.


  • 0
    L

    I don't think we need to have separate piece of code to check invalidity of last suffix. Instead it could be done as below on the fly

        map<int, vector<string>> cache;
    
    vector<string> wordBreak(string s, unordered_set<string>& wordDict ) {
    
    return wordBreak(s,wordDict,0);
    
    }
    
    vector<string> wordBreak(string &s, unordered_set<string>& wordDict, int spaceat) {
        
        vector<string> next;
        
        if(cache.find(spaceat) != cache.end())
            return cache[spaceat];
            
        if( spaceat ==s.length())
                return cache[spaceat]=next;
    
        for( int i=spaceat ; i<s.length(); i++)
        {
            string curword = s.substr(spaceat ,i-spaceat+1);
            
            if( wordDict.find( curword ) !=wordDict.end() )
            {
                 vector<string> bel= wordBreak(s,wordDict,i+1);
                 //check if the last suffix is valid
                 if( bel.size()==0 && (i+1)==s.length())
                      next.push_back(curword);
                 for( string p: bel )
                 {
                      next.push_back(curword+" "+p);
                 }
             
            }
            
        }
        return cache[spaceat]=next;
    }

  • 0
    J

    we have to check the false situation first. But I think the way we check must like what we do in wordBreakI, see if the test case is "a...aba...ac", ["a","aa","aaa","ac"],this answer will get TLE.


  • 0
    J

    This solution now gets TLE.


  • 1
    Z

    This answer is really TLE now, Contributing my answer based on the word break 1;
    The idea is easy, we use the method in word break 1, instead of using boolean variable to indicate whether this position can be split, we record the position of last string.

    For example,

    s = "catsanddog",
    dict = ["cat", "and", "sand", "dog"].

    instead of recording true in position 0, 3, 7, 9, we record more specific information in corresponding place.
    0 -1 -1 0 -1 -1 -1 3 -1 7 from the array[0…9], and than we extract the corresponding substring according to the index of this array. For example, a[9] = 7, we can s[7…9]= dog, s[7] = 3, so s[3…7] = sand, so on and so forth. But there is a problem, there may be two ways to choose for one position(just like the example provided by leetcode of this problem), So we can use a map to store it.

    The following is my code

    class Solution {

    public:

    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        int n = s.size();
        
        unordered_map<int, set<int> > f;
                
        f[0].insert(0);
        for (int i = 1; i <= n; i++) {
            for (string w : wordDict) {
                int length = w.length();
                if (length <= i && !f[i-length].empty() && s.substr(i-length, length) == w) {
                    f[i].insert(i-length);
                }
            }
        }
        
        
        vector<string> res;
        
        if (f[n].empty()) {
            return res;
        }
        
        string str;
        // extract the string
        DFS(f, str, n, res, s);
        
        return res;
    }
    
    void DFS (unordered_map<int, set<int> >& f, string str, int n, vector<string>& res, string s) {
        if (n == 0) {
            res.push_back(str);
            return;
        }
        
        for (int next : f[n]) {
            if (str.empty()) {
                DFS(f, s.substr(next, n-next), next, res, s);
            } else {
                DFS(f, s.substr(next, n-next) + " " + str, next, res, s);
            }
        }
    }
    

    };


  • 0
    G

    This is also TLE


  • 1
    A

    fixed TLE (Added a HashMap):

    public class Solution {
    
        HashMap<String, List<String>> map = new HashMap<String, List<String>>();
        
        public List<String> wordBreak(String s, Set<String> wordDict) {
         
         List<String> result = new ArrayList<String>();
         
         for(int j=s.length()-1;j>=0;j--){
             
             if (map.containsKey(s)) 
                return map.get(s);
             
             if(wordDict.contains(s.substring(j))){
                 break;
             }
             else{
                 if(j==0){
                     return result;
                 }
             }
         }
         
         for(int i=0; i < s.length() - 1; i++){
             
             if(wordDict.contains(s.substring(0,i+1))){
                 
                 List<String> strings = wordBreak(s.substring(i+1, s.length()), wordDict);
                 
                 if(strings.size() != 0){
                     for(String str : strings){
                          result.add(s.substring(0, i+1) + " " + str);
                     }
                 }
             }
         }
         
         map.put(s,result);
         
         if(wordDict.contains(s)){
             result.add(s);
         }
        return result; 
        }
    }
    

Log in to reply
 

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