@Yano 2019-09-20T02:49:08.000000Z 字数 4249 阅读 1666

# LeetCode Breadth First Search 题目汇总

LeetCode

# 公众号

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

https://github.com/LjyYano/Thinking_in_Java_MindMapping

## 题目描述

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;    }}

## 题目描述

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.

## 分析

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;    }}

• 私有
• 公开
• 删除