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

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

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)