C++ 8mm DP + DFS backtracking


  • 0
    L
    class Solution {
    public:
    void dfs(vector<bool>  &space_loc, int loc, string si, string &s, vector<string> &sv, unordered_set<string> &wordDict){
        if(loc == 0){ 
            sv.push_back(si);
        }else{
            for(int i = 0; i < loc; i++){
                if(space_loc[i] && wordDict.find(s.substr(i, loc - i)) != wordDict.end() ){
                    dfs(space_loc, i, s.substr(i, loc - i) + " " + si, s, sv, wordDict) ;
                }
            }
        }   
    }
    
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        vector<string> ret(0) ;
        int len = s.length(), max_dict_length = 0;
        vector<bool> space_loc(len+1, false);
        space_loc[0] = true;
        for(auto iter = wordDict.begin(); iter != wordDict.end(); iter++){
            max_dict_length = max_dict_length < iter->length() ? iter->length() : max_dict_length;
        }
        for(int i = 0 ; i < len ; i ++){
            if(space_loc[i] ){
                for(int j = i + 1; j < len + 1 && j - i <= max_dict_length ; j++){    
                    if(wordDict.find(s.substr(i, j - i) ) != wordDict.end() ) { 
                        space_loc[j] = true;
                    }   
                }   
                if(space_loc[i] && wordDict.find(s.substr(i, len - i)) != wordDict.end() ){
                    dfs(space_loc, i, s.substr(i, len - i), s, ret, wordDict);
                }    
            }
        }   
    
        return ret;
    }
    
    };

Log in to reply
 

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