LeetCode Breadth First Search 题目汇总

LeetCode

公众号

coding 笔记、点滴记录，以后的文章也会同步到公众号（Coding Insight）中，希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping

127 Word Ladder

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

题目描述

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:

Only one letter can be changed at a time.
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"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

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.

代码

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        LinkedList<String> queue = new LinkedList<>();
        // 在队列中放入初始元素
        queue.offer(beginWord);
        int step = 2;
        while (!queue.isEmpty()) {
            // 下一步具有的节点数
            int size = queue.size();
            while (size > 0) {
                String currString = queue.poll();
                Iterator<String> iterator = set.iterator();
                while (iterator.hasNext()) {
                    String next = iterator.next();
                    int diff = diff(next, currString);
                    // 若当前元素与取出元素差1，并且是endWord，则直接返回结果
                    if (diff == 1 && next.equals(endWord)) {
                        return step;
                    }
                    // 差1就放入队列，并将其删除（此元素可以删除，因为循环读取时长度不是最优解）
                    if (diff == 1) {
                        queue.offer(next);
                        iterator.remove();
                    }
                }
                size--;
            }
            step++;
        }
        return 0;
    }
    private int diff(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return 0;
        }
        int diff = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diff++;
            }
            if (diff >= 2) {
                return 2;
            }
        }
        return diff;
    }
}

126 Word Ladder II

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

题目描述

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time
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.

分析

部分可以依照上一题，但是这道题是求「所有的最短路径」，而不是「最短路径长度」，单纯的 BFS 无法实现。但是可以使用 BFS 构造数据结构（保证最短路径），并使用 DFS 求路径。

Version 1：没有构造通用的数据结构，map 的 value 记录步骤，在 DFS 时也要重新计算两个字符串差异数。用 set 表示是否 visit 过。

代码

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        // value：从begin到达该key的最短长度。
        Map<String, Integer> map = new HashMap<>();
        Set<String> notVisitSet = new HashSet<>(wordList);
        List<List<String>> ans = new ArrayList<>();
        if (!notVisitSet.contains(endWord)) {
            return ans;
        }
        // 构建map
        bfs(beginWord, endWord, map, notVisitSet);
        if (map.isEmpty()) {
            return ans;
        }
        map.put(beginWord, 0);
        // 从end指向begin，否则会超时！因为begin后面可能接多个路径，但是end只有一个
        dfs(endWord, beginWord, map, ans, new ArrayList<>(Arrays.asList(endWord)));
        return ans;
    }
    private void bfs(String beginWord, String endWord, Map<String, Integer> map, Set<String> notVisitSet) {
        LinkedList<String> queue = new LinkedList<>();
        // 在队列中放入初始元素
        queue.offer(beginWord);
        boolean find = false;
        int level = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                String curr = queue.poll();
                Iterator<String> iterator = notVisitSet.iterator();
                while (iterator.hasNext()) {
                    String next = iterator.next();
                    int diff = diff(curr, next);
                    if (diff == 1) {
                        // 若在某一步找到，则当前步数结束即可
                        if (next.equals(endWord)) {
                            find = true;
                        }
                        queue.offer(next);
                        iterator.remove();
                        map.put(next, level);
                    }
                }
                size--;
            }
            if (find) {
                break;
            }
            level++;
        }
    }
    private void dfs(String beginWord, String endWord, Map<String, Integer> map, List<List<String>> ans,
            List<String> tmp) {
        if (beginWord.equals(endWord)) {
            List<String> arrayList = new ArrayList<>(tmp);
            Collections.reverse(arrayList);
            ans.add(arrayList);
            return;
        }
        for (String key : map.keySet()) {
            // 要判断 diff，因为本层和下一层没有必然联系
            if (map.get(key) == map.get(beginWord) - 1 && diff(beginWord, key) == 1) {
                tmp.add(key);
                dfs(key, endWord, map, ans, tmp);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
    private int diff(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return 0;
        }
        int diff = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diff++;
            }
            if (diff >= 2) {
                return 2;
            }
        }
        return diff;
    }
}