[Leetcode单排] 单词接龙 (N127)

search bfs

字数统计: 661阅读时长: 3 min

 2019/08/01  Share

127. Word Ladder

https://leetcode.com/problems/word-ladder/

这道题目一眼看上去很像用 DFS 去操作，但是很快就会发现实在操作不下去。从单个单词跳往下一个单词时，还是得 26 个字符替换着来。这道题需要使用 BFS 完成，可以借助队列。从 beginWord 开始，对每个位置都尝试用26种字符替换，如果新字符串在单词集合中，则继续开始下一轮。需要注意的是，单词在集合中出现的话，需要将该单词删除，比如第 N + 2 轮出现的某个单词在第 N 轮也出现的话，那第 N 轮的分支得到的轮次数自然更少。

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    if (!wordList.contains(endWord)) {
        return 0;
    }
    Set<String> wordSet = new HashSet<>(wordList);
    Queue<String> queue = new LinkedList<>();
    queue.offer(beginWord);
    int len = beginWord.length();
    int step = 0;

    while (!queue.isEmpty()) {
        ++step;
        // 对上一轮压进的所有值进行处理
        for (int size = queue.size(); size > 0; size--) {
            String word = queue.poll();
            // 针对String，获得其更改一位且在wordSet存在的值
            for (int i = 0; i < len; i++) {
                for (char j = 'a'; j < 'z'; j++) {
                    char[] arr = word.toCharArray();
                    arr[i] = j;
                    String tempWord = new String(arr);
                    if (endWord.equals(tempWord)) {
                        return step + 1;
                    }
                    if (!wordSet.contains(tempWord)) {
                        continue;
                    }
                    wordSet.remove(tempWord);
                    queue.offer(tempWord);
                }
            }
        }
    }
    return 0;
}

广度优先搜索做出来已经比较不容易了，但是性能一般，还有另一种优化解法：双向广度优先搜索。单词数量较多时，效率相差非常明显。

Runtime: 14 ms, faster than 94.73%; Memory Usage: 38.1 MB, less than 99.36%

从一个队列换成两个 Set，一个从头到尾，一个从尾到头，每轮比较两个 Set 的大小，遍历小的一方的字符串进行处理，并将新单词 Set 赋给该 Set。后续继续比较两个 Set 的大小，以此类推。

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    if (!wordList.contains(endWord)) {
        return 0;
    }
    Set<String> wordSet = new HashSet<>(wordList);
    Set<String> set1 = new HashSet<>();
    set1.add(beginWord);
    Set<String> set2 = new HashSet<>();
    set2.add(endWord);
    int len = beginWord.length();
    int step = 0;

    while (!set1.isEmpty() && !set2.isEmpty()) {
        step++;
        Set<String> tempSet = new HashSet<>();
        boolean set1Big = set1.size() > set2.size();
        Set<String> smallSet = !set1Big ? set1 : set2;
        Set<String> bigSet = set1Big ? set1 : set2;
        for (String str : smallSet) {
            for (int i = 0; i < len; i++) {
                for (char j = 'a'; j < 'z'; j++) {
                    char[] arr = str.toCharArray();
                    arr[i] = j;
                    String tempWord = new String(arr);
                    if (bigSet.contains(tempWord)) {
                        return step + 1;
                    }
                    if (!wordSet.contains(tempWord)) {
                        continue;
                    }
                    wordSet.remove(tempWord);
                    tempSet.add(tempWord);
                }
            }
        }
        if (set1Big) {
            set2 = tempSet;
        } else {
            set1 = tempSet;
        }
    }
    return 0;
}

Next Post

[Leetcode单排] 复原IP地址 (N93)
Previous Post

Clojure in Action: Clojure 构件

CATALOG

1. 127. Word Ladder

