why this not right ??


  • 0
    1

    class Solution {
    public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> current, next;
    unordered_set<string> visited;
    unordered_map<string, vector<string> > father;
    unordered_set<string>dic;//
    for (int i = 0; i < wordList.size(); i++){
    dic.insert(wordList[i]);
    }

    	bool found = false;
    
    	auto state_is_target = [&](const string &s) {return s == endWord; };
    	auto state_extend = [&](const string &s) {
    		unordered_set<string> result;
    
    		for (size_t i = 0; i < s.size(); ++i) {
    			string new_word(s);
    			for (char c = 'a'; c <= 'z'; c++) {
    				if (c == new_word[i]) continue;
    
    				swap(c, new_word[i]);
    
    				if ((dic.count(new_word) > 0 || new_word == endWord) &&!visited.count(new_word)) {
    					result.insert(new_word);
    				}
    				swap(c, new_word[i]); 
    			}
    		}
    		return result;
    	};
    	current.insert(beginWord);
    	while (!current.empty() && !found) {
    		
    		for (const auto& word : current)
    			visited.insert(word);
    		for (const auto& word : current) {
    			const auto new_states = state_extend(word);
    			for (const auto &state : new_states) {
    				if (state_is_target(state)) found = true;
    				next.insert(state);
    				father[state].push_back(word);
    		
    			}
    		}
    		current.clear();
    		swap(current, next);
    	}
    	vector<vector<string> > result;
    	if (found) {
    		vector<string> path;
    		gen_path(father, path, beginWord, endWord, result);
    	}
    	return result;
    }
    

    private:
    void gen_path(unordered_map<string, vector<string> > &father,vector<string> &path, const string &start, const string &word,vector<vector<string> > &result) {
    path.push_back(word);
    if (word == start) {
    result.push_back(path);
    reverse(result.back().begin(), result.back().end());
    }
    else {
    for (const auto& f : father[word]) {
    gen_path(father, path, start, f, result);
    }
    }
    path.pop_back();
    }
    };


Log in to reply
 

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