1
// For approach: ref: https://www.youtube.com/watch?v=ZVJ3asMoZ18&t=0s
2

3
class Solution {
4
 public:
5
  int ladderLength(string beginWord, string endWord, vector<string> &wordList) {
6
    // 1. Create a set and insert all wordList to the set to have
7
    // easy search of O(1)
8
    unordered_set<string> wordSet;
9
    bool isEndWordPresent = false;
10
    for (string s : wordList) {
11
      // Check if the destination string even present in the wordList
12
      // If not then there is no point in even trying to find the
13
      // route from source string to destination string
14
      if (!isEndWordPresent && s.compare(endWord) == 0) {
15
        isEndWordPresent = true;
16
      }
17
      wordSet.insert(s);
18
    }
19

20
    // 2. If endWord is not present in the wordList return
21
    if (!isEndWordPresent) {
22
      return 0;
23
    }
24

25
    // 3. Create a queue for BST insert the elements of currentlevel to the
26
    // queue currentLevel is defined as all the strings that can be reached from
27
    // all the strings of the previous string by just replacing one character
28
    // and the one-char-replaced-string is present in the wordSet / wordList
29
    queue<string> q;
30
    q.push(beginWord);
31
    int level = 0; // every time all the strings at this level are processed
32
                   // increment it
33

34
    // 4. Loop through all the elements in the queue
35
    while (!q.empty()) {
36
      level++;
37
      int numStringsInCurLevel = q.size();
38
      // loop through all the strings in this current level
39
      // and find out if destination can be reached before
40
      // jumping to the next level of strings added to the queue
41
      while (numStringsInCurLevel--) {
42
        string curStr = q.front();
43
        q.pop();
44

45
        for (int i = 0; i < curStr.length(); i++) {
46
          string tempStr = curStr;
47
          // Now check if swappin one char in the curStr will
48
          // lead to any string in the wordSet
49
          for (char c = 'a'; c <= 'z'; c++) {
50
            tempStr[i] = c;
51
            if (tempStr.compare(curStr) == 0) {
52
              // Ignore the same string
53
              continue;
54
            }
55
            // Check if we reached the destination
56
            if (tempStr.compare(endWord) == 0) {
57
              return level + 1;
58
            }
59
            if (wordSet.find(tempStr) != wordSet.end()) {
60
              // this string is in the set so add it to the queue
61
              // and remove it from the set
62
              q.push(tempStr);
63
              wordSet.erase(tempStr);
64
            }
65
          }
66
        }
67
      }
68
    }
69

70
    // If we are here then we couldn't reach destination
71
    // even though the destination string is present in the wordList
72
    // there is no path from source to destination for the given rules
73
    return 0;
74
  }
75
};