赞
踩
给定两个单词(beginWord 和 endWord)和一个字典 wordList,找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则:
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列,返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的,且二者不相同。
示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: []
解释: endWord "cog" 不在字典中,所以不存在符合要求的转换序列。
bfs 找最短,然后 dfs 回溯找所有的解。这道题很麻烦的是构建图。
public class Solution { public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) { // 先将 wordList 放到哈希表里,便于判断某个单词是否在 wordList 里 Set<String> wordSet = new HashSet<>(wordList); List<List<String>> res = new ArrayList<>(); if (wordSet.size() == 0 || !wordSet.contains(endWord)) { return res; } // 第 1 步:使用广度优先遍历得到后继结点列表 successors // key:字符串,value:广度优先遍历过程中 key 的后继结点列表 Map<String, Set<String>> successors = new HashMap<>(); boolean found = bfs(beginWord, endWord, wordSet, successors); if (!found) { return res; } // 第 2 步:基于后继结点列表 successors ,使用回溯算法得到所有最短路径列表 Deque<String> path = new ArrayDeque<>(); path.addLast(beginWord); dfs(beginWord, endWord, successors, path, res); return res; } private boolean bfs(String beginWord, String endWord, Set<String> wordSet, Map<String, Set<String>> successors) { Queue<String> queue = new LinkedList<>(); queue.offer(beginWord); // 记录访问过的单词 Set<String> visited = new HashSet<>(); visited.add(beginWord); boolean found = false; int wordLen = beginWord.length(); // 当前层访问过的结点,当前层全部遍历完成以后,再添加到总的 visited 集合里 Set<String> nextLevelVisited = new HashSet<>(); while (!queue.isEmpty()) { int currentSize = queue.size(); for (int i = 0; i < currentSize; i++) { String currentWord = queue.poll(); char[] charArray = currentWord.toCharArray(); for (int j = 0; j < wordLen; j++) { char originChar = charArray[j]; for (char k = 'a'; k <= 'z'; k++) { if (charArray[j] == k) { continue; } charArray[j] = k; String nextWord = new String(charArray); if (wordSet.contains(nextWord)) { if (!visited.contains(nextWord)) { if (nextWord.equals(endWord)) { found = true; } nextLevelVisited.add(nextWord); queue.offer(nextWord); // 维护 successors 的定义 successors.computeIfAbsent(currentWord, a -> new HashSet<>()); successors.get(currentWord).add(nextWord); } } } charArray[j] = originChar; } } if (found) { break; } visited.addAll(nextLevelVisited); nextLevelVisited.clear(); } return found; } private void dfs(String beginWord, String endWord, Map<String, Set<String>> successors, Deque<String> path, List<List<String>> res) { if (beginWord.equals(endWord)) { res.add(new ArrayList<>(path)); return; } if (!successors.containsKey(beginWord)) { return; } Set<String> successorWords = successors.get(beginWord); for (String nextWord : successorWords) { path.addLast(nextWord); dfs(nextWord, endWord, successors, path, res); path.removeLast(); } } }
class Solution { private static final int INF = 1 << 20; private Map<String, Integer> wordId; // 单词到id的映射 private ArrayList<String> idWord; // id到单词的映射 private ArrayList<Integer>[] edges; // 图的边 public Solution() { wordId = new HashMap<>(); idWord = new ArrayList<>(); } public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) { int id = 0; // 将wordList所有单词加入wordId中 相同的只保留一个 // 并为每一个单词分配一个id for (String word : wordList) { if (!wordId.containsKey(word)) { wordId.put(word, id++); idWord.add(word); } } // 若endWord不在wordList中 则无解 if (!wordId.containsKey(endWord)) { return new ArrayList<>(); } // 把beginWord也加入wordId中 if (!wordId.containsKey(beginWord)) { wordId.put(beginWord, id++); idWord.add(beginWord); } // 初始化存边用的数组 edges = new ArrayList[idWord.size()]; for (int i = 0; i < idWord.size(); i++) { edges[i] = new ArrayList<>(); } // 添加边 for (int i = 0; i < idWord.size(); i++) { for (int j = i + 1; j < idWord.size(); j++) { // 若两者可以通过转换得到 则在它们间建一条无向边 if (transformCheck(idWord.get(i), idWord.get(j))) { edges[i].add(j); edges[j].add(i); } } } int dest = wordId.get(endWord); // 目的ID List<List<String>> res = new ArrayList<>(); // 存答案 int[] cost = new int[id]; // 到每个点的代价 for (int i = 0; i < id; i++) { cost[i] = INF; // 每个点的代价初始化为无穷大 } // 将起点加入队列 并将其cost设为0 Queue<ArrayList<Integer>> q = new LinkedList<>(); ArrayList<Integer> tmpBegin = new ArrayList<>(); tmpBegin.add(wordId.get(beginWord)); q.add(tmpBegin); cost[wordId.get(beginWord)] = 0; // 开始广度优先搜索 while (!q.isEmpty()) { ArrayList<Integer> now = q.poll(); int last = now.get(now.size() - 1); // 最近访问的点 if (last == dest) { // 若该点为终点则将其存入答案res中 ArrayList<String> tmp = new ArrayList<>(); for (int index : now) { tmp.add(idWord.get(index)); // 转换为对应的word } res.add(tmp); } else { // 该点不为终点 继续搜索 for (int i = 0; i < edges[last].size(); i++) { int to = edges[last].get(i); // 此处<=目的在于把代价相同的不同路径全部保留下来 if (cost[last] + 1 <= cost[to]) { cost[to] = cost[last] + 1; // 把to加入路径中 ArrayList<Integer> tmp = new ArrayList<>(now); tmp.add(to); q.add(tmp); // 把这个路径加入队列 } } } } return res; } // 两个字符串是否可以通过改变一个字母后相等 boolean transformCheck(String str1, String str2) { int differences = 0; for (int i = 0; i < str1.length() && differences < 2; i++) { if (str1.charAt(i) != str2.charAt(i)) { ++differences; } } return differences == 1; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。