typedef pair<string, int> qNode;

class Solution{
	public:
		// returns if two words differ by one letter. 
		bool diffWord(const string & str1, const string & str2){
			int count = 0;

			for(int length = 0; length < str1.size() && count < 2; length++){
				if(str1[length] != str2[length]) count++;
			}
			return (count == 1);
		}
	
		int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
			if(find(wordList.begin(), wordList.end(), endWord) == wordList.end()) return 0;
        
			unordered_set<string> visited;

			queue<qNode> q;

			q.push(qNode(beginWord, 1));

			visited.insert(beginWord);

			while(!q.empty()){
				qNode const &curNode = q.front();   

				if(curNode.first == endWord) return curNode.second; 

				for(string const &word : wordList){ 
					if(find(visited.begin(), visited.end(), word) == visited.end() && diffWord(curNode.first, word)){
						visited.insert(word);
						q.push(qNode(word, curNode.second + 1));
					}
				}

				q.pop();
			}
        
			return 0;
		}
};