Word Ladder

Given a begin word, an end word and a dictionary, find the least number transformations from begin word to end word, and return the length of the transformation sequence. Return 0 if there is no such transformations.

In each transformation, you can only change one letter, and the word should still in the dictionary after each transformation.

Assumptions

1. All words have the same length.

2. All words contain only lowercase alphabetic characters.

3. There is no duplicates in the word list.

4.The beginWord and endWord are non-empty and are not the same.

Example: start = "git", end = "hot", dictionary = {"git","hit","hog","hot"}

Output: 3

Explanation: git -> hit -> hot

Solution: BFS check every transformation of each word

public class Solution {
  public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    if (beginWord.equals(endWord)) return 0;
    Set<String> isWord = new HashSet<>(wordList); //check if word in dict
    Set<String> visited = new HashSet<>(); //dedup
    Queue<String> q = new LinkedList<>();

    visited.add(beginWord);
    q.offer(beginWord);

    int count = 1;

    while(!q.isEmpty()){ //BFS
      int size = q.size(); //current layer width
      count++;
      for (int i = 0; i < size; i++){
        String current = q.poll();
        boolean foundEnd = addNeighbors(current, q, visited, isWord, endWord);
        if (foundEnd) return count;
      }
    }
    return 0;
  }

  private boolean addNeighbors(String word, Queue<String> q, Set<String> visited, Set<String> isWord, String endWord){
    StringBuilder sb = new StringBuilder(word);
    visited.add(word);
    //every letter at every index
    for (int i = 0; i < word.length(); i++){
      char orig = word.charAt(i);
      for(char j = 'a'; j <= 'z'; j++){
        if (j == orig) continue;
        sb.setCharAt(i, j);
        String modifiedWord = sb.toString();
        if (modifiedWord.equals(endWord)) return true; //generated target word
        if (isWord.contains(modifiedWord) && !visited.contains(modifiedWord)){
          q.offer(modifiedWord);
        }
      }
      sb.setCharAt(i, orig);
    }
    return false;
  }
}

For N words of M length

TC: O(M * 25 * N)

SC: O(N)

Mistakes Made:

1. dont search every word if only transformations of word need to be checked. O(25 * M) vs O(N * M)

2. dont add word to visited until you visit/expand it

3. start count at 1 because the output length includes the initial word