127. Word Ladder

• Time: $O(|\texttt{wordList}| \cdot 26^{\texttt{wordlist[i]}})$
• Space: $O(|\texttt{wordList}|)$

C++JavaPython

class Solution {
 public:
  int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> wordSet(wordList.begin(), wordList.end());
    if (!wordSet.contains(endWord))
      return 0;

    queue<string> q{{beginWord}};

    for (int step = 1; !q.empty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        string word = q.front();
        q.pop();
        for (int i = 0; i < word.length(); ++i) {
          const char cache = word[i];
          for (char c = 'a'; c <= 'z'; ++c) {
            word[i] = c;
            if (word == endWord)
              return step + 1;
            if (wordSet.contains(word)) {
              q.push(word);
              wordSet.erase(word);
            }
          }
          word[i] = cache;
        }
      }

    return 0;
  }
};

class Solution {
  public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord))
      return 0;

    Queue<String> q = new ArrayDeque<>(List.of(beginWord));

    for (int step = 1; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        StringBuilder sb = new StringBuilder(q.poll());
        for (int i = 0; i < sb.length(); ++i) {
          final char cache = sb.charAt(i);
          for (char c = 'a'; c <= 'z'; ++c) {
            sb.setCharAt(i, c);
            final String word = sb.toString();
            if (word.equals(endWord))
              return step + 1;
            if (wordSet.contains(word)) {
              q.offer(word);
              wordSet.remove(word);
            }
          }
          sb.setCharAt(i, cache);
        }
      }

    return 0;
  }
}

class Solution:
  def ladderLength(
      self,
      beginWord: str,
      endWord: str,
      wordList: list[str],
  ) -> int:
    wordSet = set(wordList)
    if endWord not in wordSet:
      return 0

    q = collections.deque([beginWord])

    step = 1
    while q:
      for _ in range(len(q)):
        wordList = list(q.popleft())
        for i, cache in enumerate(wordList):
          for c in string.ascii_lowercase:
            wordList[i] = c
            word = ''.join(wordList)
            if word == endWord:
              return step + 1
            if word in wordSet:
              q.append(word)
              wordSet.remove(word)
          wordList[i] = cache
      step += 1

    return 0