Woord Ladder

You are given 2 words beginWord and endWord.
You need to return the number of words, that will transform from beginWord to endWord

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

This question can be solved in 2 ways.
1. BFS
2. 2 end BFS

1. Solving using regular BFS:

So the question gives us starting word and ending word, and a word dictionary. The goal here is to see if there is a way from starting word to ending word by changing only one letter at a time.

One simple way is the brute force method, that traverses all the cases.

If we consider our example, the starting word is “hit”, we start by replacing from the starting letter “ait” “bit” “cit” … “yit” “zit”, if any word is present in the dictionary, then save that word. When we reach “hot”, we save it, then again start with the first character “cot” “dot”, now “dot” is also present, save it.

Hence we use BFS instead of DFS, because, BFS ensures the shortest path.

2. Solving using 2 end BFS.

In this solution we start the path simultaneously from the start word and end word and merge in middle.

/*
* File     : word_ladder.cpp
*/

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<queue>

using namespace std;

int ladderLength_bfs(string beginWord, string endWord, vector<string>& wordList) 
{
  unordered_set<string> wordSet(wordList.begin(), wordList.end());
  unordered_map<string, int> pathCnt{{{beginWord, 1}}};
  queue<string> q{{beginWord}};
  
  while (!q.empty()) 
  {
    string word = q.front(); q.pop();
    for (int i = 0; i < word.size(); ++i) 
    {
      string newWord = word;
      for (char ch = 'a'; ch <= 'z'; ++ch) 
      {
        newWord[i] = ch;
        if (wordSet.count(newWord) && newWord == endWord) 
          return pathCnt[word] + 1;
        if (wordSet.count(newWord) && !pathCnt.count(newWord)) 
        {
          q.push(newWord);
          pathCnt[newWord] = pathCnt[word] + 1;
        }   
      }
    }
  }
  return 0;
}

int ladderLength_two_end_bfs(string beginWord, string endWord, vector<string>& wordList) 
{
  unordered_set<string> dict(wordList.begin(), wordList.end());
  if (dict.count(endWord) == 0) return 0;

  unordered_set<string> string1 = {beginWord};
  unordered_set<string> string2 = {endWord};
  dict.erase(endWord);
  int step = 0;

  while (!string1.empty() && !string2.empty()) 
  {
      step++;
      if (string1.size() > string2.size()) swap(string1, string2);
      unordered_set<string> temp;

      for (auto word : string1) 
      {
          for (int i=0; i<word.size(); i++) 
          {
              char oldChar = word[i];
              for (char c='a'; c<='z'; c++) 
              {
                  if (c == oldChar) continue;
                  string newWord = word;
                  newWord[i] = c;
                  if (string2.count(newWord)) 
                    return step+1;

                  if (dict.count(newWord)) 
                  {
                      temp.insert(newWord);
                      dict.erase(newWord);
                  }
              }
          }
      }
      swap(string1, temp);
  }
  return 0;
}


int main() 
{ 
    vector<string> wordList; 
    wordList.push_back("hot");
    wordList.push_back("dot");
    wordList.push_back("dog");
    wordList.push_back("lot");
    wordList.push_back("log");
    wordList.push_back("cog");
    string beginWord  = "hit"; 
    string endWord  = "cog"; 

    cout << "Length of shortest chain using one end BFS is: "<< ladderLength_bfs(beginWord, endWord, wordList)<<endl;  
    cout << "Length of shortest chain using two end BFS is: "<< ladderLength_two_end_bfs(beginWord, endWord, wordList)<<endl;  

    return 0;  
}