findLadders--BFS--a到z每个字母尝试着换。

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

unordered_set state_extend_function(const string &s,
	const unordered_set &dict, unordered_set visited,string end) {
	unordered_set result;
	for (size_t i = 0; i 		string new_word(s);
		for (char c = 'a'; c <= 'z'; c++) {
			if (c == new_word[i]) continue;
			swap(c, new_word[i]);
			if ((dict.count(new_word) > 0 || string(new_word) == string(end) ) &&
				!visited.count(new_word)) {
					result.insert(new_word);
			}
			swap(c, new_word[i]); // 恢复该单词
		}
	}
	return result;
}

vector > findLadders(string start, string end,
	const unordered_set &dict) {
		unordered_set current, next; // 当前层，下一层，用集合是为了去重
		unordered_set visited; // 判重
		unordered_map > father; // 树
		bool found = false;
		auto state_is_target = [&](const string &s) {
			return s == end;
		};

		current.insert(start);
		while (!current.empty() && !found) {
			// 先将本层全部置为已访问，防止同层之间互相指向for (const auto& word : current)
			unordered_set::iterator it;
			for ( it=current.begin();it != current.end();it++  ){
				string word=*it;
				visited.insert(word);
			}

			unordered_set::iterator itc;
			for ( itc=current.begin();itc != current.end();itc++  ){
				string word=*itc;
				unordered_set new_states = state_extend_function(word,dict,visited,end);
				unordered_set::iterator itv;
				for ( itv=new_states.begin();itv != new_states.end();itv++  ){
					string state=*itv;
				
				// for (const auto&state : new_states) {
					if (state_is_target(state)) found = true;
					next.insert(state);
					father[state].push_back(word);
					// visited.insert(state); // 移动到最上面了
				}
			}
			current.clear();
			swap(current, next);
		}
		vector > result;
		if (found) {
			vector path;
			gen_path(father, path, start, end, result);
		}
		return result;
}