> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/bfs/word-ladder.md).

# 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

```java
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