Share my dfs C++ solution on 7ms


  • 0
    R

    class Solution {
    public:

    // compare if the suffix is contained in the word
    bool stringSuffComp(const string& suff, const string& word){
    
    	if (suff.length() > word.length()) return false;
    
    	for (int i = suff.length() - 1, j = word.length() - 1; i >= 0 && j >= 0; i--, j--){
    	
    		if (suff[i] != word[j]) return false;
    	}
    	return true;
    }
    
    // check if any suffix of s is not contained in the dict
    // only check those suffix that is shorter than the minimum length of the words in dict
    bool checkSuffix(string* s, unordered_set<string> &dict){
    	
    	string suff;
    	unordered_set<string>::iterator j = dict.begin();
    	// Record the minimum length of the words, help check the suffix
    	int suffLen = (*s).length();
    	while (j != dict.end()){
    
    		if ((*j).length() < suffLen) suffLen = (*j).length();
    		j++;
    	}
    
    	j = dict.begin();
    	// check if the suffix of string is contained as the suffix of each word
    	for (int i = (*s).length() - 1; i >= (*s).length() - suffLen; i--){
    	
    		if (i < 0) break;
    		suff = (*s).substr(i);
    		bool found = false;
    		while (j != dict.end()){
    		
    			if (stringSuffComp(suff, (*j))) { 
    				found = true; 
    				break;
    			}
    			j++;
    		}
    		if (!found) return false;
    	}
    	return true;
    }
    
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
    
    	stack<int> nodes;						// when we have a guess, put idx of that word into this record
    	stack<string> str_nodes;				// record the sentence that is matched so forth
    	vector<string> res;
    	string* ans = new string("");
    	int i = 0, j = 1;						// start and end pos of current word search
    	bool finish = false;
    
    	if (!checkSuffix(&s, dict)) return res;	// branch-cutting? get rid of the cases that would fail but exetremely costy
    
    	while (!finish){
    
    		for (; j <= s.length(); j++){
    			// search possible current word
    			if (dict.find(s.substr(i, j - i)) == dict.end()) continue;
    			else if (j == s.length()){
    				// a match here, and we have a new sentence with space
    				*ans += s.substr(i, j - i);
    				res.push_back(*ans);
    				ans = new string("");
    				if (nodes.size()) break;
    			}
    			else{
    				// a matched word, but not reach the end of original string	
    				str_nodes.push(string(*ans));
    				*ans += s.substr(i, j - i) + " ";
    				nodes.push(j);
    				nodes.push(i);
    
    				i = j;
    				continue;
    			}
    		}
    		// the last guess is not a good one, pop out and retry
    		if (nodes.size()){
    			*ans = str_nodes.top(); str_nodes.pop();
    			i = nodes.top(); nodes.pop();
    			j = nodes.top(); nodes.pop();
    			j++;
    		}
    		else break;
    	}
    	return res;
    }
    

    };


Log in to reply
 

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