C++ solution using dfs + dp + and graph


  • 0

    dp[i] is using the same approach from word break to determine if [0, i - 1] can be built using dictionary. Then for each i, build adjacency lists adj for all the possible j that [i, j] is a word in dictionary, so now it's like to solve a graph problem. This may not be the most optimal compared to other 4 ms solutions, just to share. For improvement, as suggested by other posts, find the minlen, maxlen of word length in dictionary can definitely cut down the run time in loop when building adj lists.

    8 ms (with improvement)

    class Solution {
    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            vector<string> all;
            int n = s.size(), i, minLen = INT_MAX, maxLen = INT_MIN;
            vector<bool> dp(n + 1, false);
            vector<vector<int>> adj(n, vector<int>());
            
            for(auto word: wordDict){
                minLen = min(minLen, (int)word.size());
                maxLen = max(maxLen, (int)word.size());
            }
            // build dp and adj at the same time
            for(i = 0, dp[0] = true; i < n; i++){
                for(int len = minLen; len <= min(maxLen, n - i); len++){
                    if(dp[i] && wordDict.find(s.substr(i, len)) != wordDict.end()){ 
                        adj[i].push_back(i + len - 1);
                        dp[i + len] = true;
                    }
                }
            }  
            
            if(dp[n]) dfs(s, 0, "", all, dp, adj);        
            return all;
        }
        
        void dfs(string s, int start, string oneSol, vector<string>& all, vector<bool>& dp, vector<vector<int>> &adj)
        {
            if(!dp[start]) return;
            for(auto i: adj[start]){
                string word = s.substr(start, i - start + 1);
                if(i == s.size() - 1) {
                    all.push_back(oneSol + word); 
                    return;    
                }
                dfs(s, i + 1, oneSol + word + " ", all, dp, adj);
            }
        }
    };
    

    24 ms

    class Solution { 
    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            vector<string> all;
            int n = s.size();
            
            vector<bool> dp(n + 1, false);
            dp[0] = true;
            vector<vector<int>> adj(n, vector<int>());
            
            for(int i = 0; i < s.size(); i++){
                for(int j = i; j < s.size(); j++){
                    if(dp[i] && wordDict.find(s.substr(i, j - i + 1)) != wordDict.end()){ 
                        adj[i].push_back(j);
                        dp[j + 1] = true;
                    }
                }
            }  
            
            if(dp[n]) dfs(s, 0, "", all, dp, adj);        
            return all;
        }
        
        void dfs(string s, int start, string oneSol, vector<string>& all, vector<bool>& dp, vector<vector<int>> &adj)
        {
            if(!dp[start]) return;
            for(auto i: adj[start]){
                string word = s.substr(start, i - start + 1);
                if(i == s.size() - 1) {
                    all.push_back(oneSol + word); 
                    return;    
                }
                dfs(s, i + 1, oneSol + word + " ", all, dp, adj);
            }
        }
    };

Log in to reply
 

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