LeetCode Q127: Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Solution:

Using BFS and start at two ends in the same time.

	class Solution {
	public:
	int helper(queue<string>& sWord, queue<string>& eWord, int sHubs, int eHubs,
	unordered_map<string, bool>& wordList,
	unordered_map<string, bool>& sMap, unordered_map<string, bool>& eMap){
	int s=sWord.size();
	bool sFindNewWord=false;
	for(int i=0; i<s; i++){
	string w=sWord.front();
	sWord.pop();
	if(eMap[w]==true)
	return sHubs+eHubs;
	for(int j=0; j<w.length(); j++)
	for(int k=0; k<26; k++){
	string tmp=w;
	tmp[j]='a'+k;
	if(sMap[tmp]!=true&&wordList[tmp]==true){
	sWord.push(tmp);
	sMap[tmp]=true;
	sFindNewWord=true;
	}
	}
	}
	sHubs=sFindNewWord? sHubs+1:sHubs;
	int e=eWord.size();
	bool eFindNewWord=false;
	for(int i=0; i<e; i++){
	string w=eWord.front();
	eWord.pop();
	if(sMap[w]==true)
	return sHubs+eHubs;
	for(int j=0; j<w.length(); j++)
	for(int k=0; k<26; k++){
	string tmp=w;
	tmp[j]='a'+k;
	if(eMap[tmp]!=true&&wordList[tmp]==true){
	eWord.push(tmp);
	eMap[tmp]=true;
	eFindNewWord=true;
	}
	}
	}
	eHubs=eFindNewWord? eHubs+1:eHubs;
	if(!sFindNewWord&&!eFindNewWord)
	return 0;
	else
	return helper(sWord, eWord, sHubs, eHubs, wordList, sMap, eMap);
	}
	int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
	unordered_map<string, bool> myMap;
	for(auto it =wordList.begin(); it!=wordList.end(); it++)
	myMap[*it]=true;
	queue<string> sWord;
	queue<string> eWord;
	unordered_map<string, bool> sMap;
	unordered_map<string, bool> eMap;
	sWord.push(beginWord);
	eWord.push(endWord);
	sMap[beginWord]=true;
	eMap[endWord]=true;
	int sHubs=1;
	int eHubs=1;
	return helper(sWord, eWord, sHubs, eHubs, myMap, sMap, eMap);
	}
	};

view raw Q127WordLadder.cpp hosted with ❤ by GitHub