LeetCode 127. Word Ladder

单词接龙

Question

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, 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.

Note:

• Return 0 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.

Example 1:

Input:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

Output: 5

Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.
Example 2:

Input:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

Output: 0

Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.

Solution

采用广度优先算法(BFS)

• 增加附加类来标识遍历节点，包含当前节点的单词跟对应的树的层次
• 不采用辅助函数，因为采用辅佐函数就时间复杂度是NL（N是wordList的长度，L是单词的长度），题目有个特性是都是a-z的字符，说明只需遍历L*26次就可以穷举邻居，这个时间复杂度上要少很多
• 时间复杂度 O(n*26^l) 空间复杂度 O(n)

Runtime: 53 ms, faster than 83.76% of Java online submissions for Word Ladder.
Memory Usage: 39.5 MB, less than 84.04% of Java online submissions for Word Ladder.

class Solution {
    class Node {
        public String word;
        public int level; // current word's level
        public Node(String word, int level) {
            this.word = word;
            this.level = level;
        }
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) return 0;
        Set<String> wordSet = new HashSet<>(wordList); // avoid the loop case
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(beginWord, 1));

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            if (node.word.equals(endWord)) { // match!
                return node.level;
            }

            // find the neighbor word list

            for (int i = 0; i < node.word.length(); ++i) {
                char[] raw = node.word.toCharArray();
                for (char j = 'a'; j <= 'z'; ++j) {
                    raw[i] = j;
                    String tmp = new String(raw);
                    if (wordSet.contains(tmp)) {
                        wordSet.remove(tmp);
                        queue.offer(new Node(tmp, node.level + 1));
                    }
                }
            }
        }
        return 0;
    }
}

采用双向广度优先算法(Bi-BFS)

• 跟前面解题方法类似，但是区别是分别从起点跟终点来触发找邻居集合（子节点集合）
• 在查找过程中，需要交替找下集子节点集合，这里通过判断上下两个集合集的大小
• 最后发现他们会在中间层相遇，形成一个菱形的树状接口
• 时间复杂度 O(n*26^l/2) 空间复杂度 O(n)

Runtime: 14 ms, faster than 98.75% of Java online submissions for Word Ladder.
Memory Usage: 39.8 MB, less than 80.62% of Java online submissions for Word Ladder.

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

        Set<String> p1 = new HashSet<String>(){{add(beginWord);}};
        Set<String> p2 = new HashSet<String>(){{add(endWord);}};
        int cnt = 0; // the level

        while (!p1.isEmpty() && !p2.isEmpty()) {
            cnt++;

            // make from the smaller set to find neighbors
            if (p1.size() > p2.size()) {
                Set<String> tmp = p1;
                p1 = p2;
                p2 = tmp;
            }

            // next neighbors in set
            Set<String> p = new HashSet<>();
            for (String word : p1) {
                for (int i = 0; i < word.length(); ++i) {
                    char[] raw = word.toCharArray();
                    for (char j = 'a'; j <= 'z'; ++j) {
                        raw[i] =j;
                        String tmp = new String(raw);
                        if (p2.contains(tmp)) return ++cnt; // match! this should be first, as wordSet may be empty
                        if (!wordSet.contains(tmp)) continue;
                        p.add(tmp);
                        wordSet.remove(tmp);
                    }
                }
            }
            p1 = p;
        }
        return 0;
    }
}