# 127 Word Ladder

## 127. Word Ladder

## 1. Question

Given two words (beginWordandendWord), and a dictionary's word list, find all shortest transformation sequence(s) frombeginWordtoendWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:\
beginWord=`"hit"`\
endWord=`"cog"`\
wordList=`["hot","dot","dog","lot","log","cog"]`

Return

```
  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]
```

**Note:**

* Return an empty list if there is no such transformation sequence.
* All words have the same length.
* All words contain only lowercase alphabetic characters.
* You may assume no duplicates in the word list.
* You may assume beginWord and endWord are non-empty and are not the same.

## 2. Implementation

**(1) BFS**

```java
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (wordList.size() == 0) {
            return 0;
        }

        Set<String> dict = new HashSet<>();

        for (String word : wordList) {
            dict.add(word);
        }

        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);

        Set<String> visited = new HashSet<>();
        visited.add(beginWord);

        int len = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                String curWord = queue.remove();

                if (curWord.equals(endWord)) {
                    return len;
                }

                char[] letters = curWord.toCharArray();
                for (int j = 0; j < curWord.length(); j++) {
                    char oldC = letters[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        letters[j] = c;

                        String nextWord = new String(letters);

                        if (dict.contains(nextWord) && !visited.contains(nextWord)) {
                            visited.add(nextWord);
                            queue.add(nextWord);
                            dict.remove(nextWord);
                        }
                    }
                    letters[j] = oldC;
                }
            }
            ++len;
        }
        return 0;
    }
}
```

(2) Bi-directional BFS

```java
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (wordList.size() == 0) {
            return 0;
        }

        Set<String> dict = new HashSet<>();

        for (String word : wordList) {
            dict.add(word);
        }

        if (!dict.contains(endWord)) {
            return 0;
        }

        Set<String> visited = new HashSet<>();
        Set<String> begin = new HashSet<>();
        Set<String> end = new HashSet<>();

        begin.add(beginWord);
        end.add(endWord);

        int len = 1;

        while (!begin.isEmpty() && !end.isEmpty()) {
            if (begin.size() > end.size()) {
                Set<String> set = begin;
                begin = end;
                end = set;
            }

            Set<String> temp = new HashSet<>();

            for (String word : begin) {                
                char[] letters = word.toCharArray();

                for (int i = 0; i < letters.length; i++) {
                    char oldC = letters[i];

                    for (char c = 'a'; c <= 'z'; c++) {
                        letters[i] = c;

                        String nextWord = new String(letters);

                        if (end.contains(nextWord)) {
                            return len + 1;
                        }


                        if (dict.contains(nextWord) && !visited.contains(nextWord)) {
                            visited.add(nextWord);
                            temp.add(nextWord);
                        }
                    }
                    letters[i] = oldC;
                }
            }
            ++len;
            begin = temp;
        }
        return 0;
    }
}
```

## 3. Time & Space Complexity

BFS: 时间复杂度:O(n \* L \* 26),其中n为word的个数，L为每个word的平均长度， 空间复杂度: O(n)