算法細(xì)節(jié)系列（20）：Word Ladder系列

詳細(xì)代碼可以fork下Github上leetcode項(xiàng)目，不定期更新。

題目摘自leetcode：
1. Leetcode 127: Word Ladder
2. Leetcode 126: Word Ladder II

Leetcode 127: Word Ladder

Problem:

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.

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.

這道題其實(shí)不難，但要想到這種解法卻要費(fèi)一番周折，如果對(duì)最短路徑搜索熟悉的話，相信你一眼就能看出答案了，并且我們要論證一點(diǎn)，為什么最短路徑算法對(duì)這道題來(lái)說(shuō)是正確解法。

我的思路：
DFS，把所有編輯距離為1的單詞連接在一塊，構(gòu)建一個(gè)MAP（鄰接矩陣）。這樣之后，我們就可以從beginWord開(kāi)始DFS搜索了，中間需要狀態(tài)記錄。代碼如下：

public int ladderLength(String beginWord, String endWord, List<String> wordList) {Map<String, List<String>> map = new HashMap<>();map.put(beginWord, new ArrayList<>());for (String word : wordList){map.put(word, new ArrayList<>());}for (String key : map.keySet()){List<String> container = map.get(key);for (String word : wordList){if (oneDiff(key, word)){container.add(word);}}map.put(key, container);}int ans = helper(map, beginWord, endWord, new HashSet<>());return ans >= 1 << 30 ? 0 : ans;}private int helper(Map<String, List<String>> map,String beginWord, String endWord, Set<String> visited){if (visited.contains(beginWord)) return 1<<30;visited.add(beginWord);for (String find : map.get(beginWord)){if (find.equals(endWord)){visited.remove(beginWord);return 2;}}int min = Integer.MAX_VALUE;for (String find : map.get(beginWord)){int x = 1 + helper(map, find, endWord, visited);min = Math.min(min, x);}visited.remove(beginWord);return min;}private boolean oneDiff(String a, String b){if (a.equals(b)) return false;char[] aa = a.toCharArray();char[] bb = b.toCharArray();int oneDiff = 0;for (int i = 0; i < aa.length; i++){if (aa[i] != bb[i]){oneDiff ++;if (oneDiff >= 2) return false;}}return true;}

代碼沒(méi)有多大問(wèn)題，典型的DFS+狀態(tài)回溯，遍歷搜索每一條到達(dá)endWord的路徑，找尋最短路徑。但很可惜TLE了，直觀上來(lái)看是因?yàn)闉榱四玫降絜ndWord的最短路徑，我們需要遍歷每一條到endWord的路徑，這是遞歸求解的一個(gè)特點(diǎn)。但實(shí)際情況，我們可以省去某些點(diǎn)的遍歷。

就那這個(gè)問(wèn)題來(lái)說(shuō)，如從beginWord開(kāi)始搜索，如

beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log","cog"] wordList中編輯距離為1的單詞有： a. hot 此時(shí)BFS搜索與"hot"最近距離的單詞，有： a. dot b. lot 再BFS搜索"dot"時(shí)，有： a. cog 所以我們只需要BFS三次就能得到正確答案，而DFS中，需要DFS至少三次。

上述過(guò)程就是經(jīng)典的Dijkstra算法，代碼如下：

public int ladderLength(String beginWord, String endWord, List<String> wordList) {List<String> reached = new ArrayList<>();reached.add(beginWord);Set<String> wordSet = new HashSet<>(wordList);if(!wordSet.contains(endWord)) return 0;wordSet.add(endWord);int distance = 1;while (!reached.contains(endWord)){ //到達(dá)該目的地List<String> toAdd = new ArrayList<>();for (String each : reached){for (int i = 0; i < each.length(); i++){char[] chars = each.toCharArray();for (char c = 'a'; c <= 'z'; c++){chars[i] = c;String wd = new String(chars);if (wordSet.contains(wd)){toAdd.add(wd);wordSet.remove(wd); //記錄訪問(wèn)狀態(tài)}}}}distance ++;if (toAdd.size() == 0) return 0; //沒(méi)有編輯距離為1的單詞reached = toAdd;}return distance;}

Leetcode 126: Word Ladder II

Problem:

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.

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.

這道題的思路讓我對(duì)DFS和BFS有了一些基本理解，但還不夠深刻，咋說(shuō)呢，我沒(méi)想到BFS和DFS還可以分工合作，BFS用來(lái)快速求出最小distance，而DFS則用來(lái)遍歷所有路徑，兩種遍歷方法各有長(zhǎng)處，綜合起來(lái)就能解決該問(wèn)題了，所以我寫(xiě)了一個(gè)版本，代碼如下：

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {Map<String, List<String>> map = new HashMap<>();map.put(beginWord, new ArrayList<>());for (String word : wordList){map.put(word, new ArrayList<>());}for (String key : map.keySet()){List<String> container = map.get(key);for (String word : wordList){if (oneDiff(key, word)){container.add(word);}}map.put(key, container);}int distance = bfs(beginWord, endWord, wordList);List<List<String>> ans = new ArrayList<>();dfs(map, beginWord, endWord, ans, new ArrayList<>(), distance);return ans;}private void dfs(Map<String, List<String>> map,String beginWord, String endWord, List<List<String>> ans, List<String> path, int distance){path.add(beginWord);if (distance == 0){path.remove(path.size()-1); return;}if (beginWord.equals(endWord)){ans.add(new ArrayList<>(path));path.remove(path.size()-1);return;}for (String find : map.get(beginWord)){dfs(map, find, endWord, ans, path, distance-1);}path.remove(path.size()-1);}private int bfs(String beginWord, String endWord, List<String> wordList) {List<String> reached = new ArrayList<>();reached.add(beginWord);Set<String> wordSet = new HashSet<>(wordList);if(!wordSet.contains(endWord)) return 0;wordSet.add(endWord);int distance = 1;while (!reached.contains(endWord)){ //達(dá)到該目的地List<String> toAdd = new ArrayList<>();for (String each : reached){for (int i = 0; i < each.length(); i++){char[] chars = each.toCharArray();for (char c = 'a'; c <= 'z'; c++){chars[i] = c;String wd = new String(chars);if (wordSet.contains(wd)){toAdd.add(wd);wordSet.remove(wd);}}}}distance ++;if (toAdd.size() == 0) return 0;reached = toAdd;}return distance;}private boolean oneDiff(String a, String b){if (a.equals(b)) return false;char[] aa = a.toCharArray();char[] bb = b.toCharArray();int oneDiff = 0;for (int i = 0; i < aa.length; i++){if (aa[i] != bb[i]){oneDiff ++;if (oneDiff >= 2) return false;}}return true;}

思路相當(dāng)清楚了，以為能夠AC，結(jié)果發(fā)現(xiàn)TLE了，說(shuō)明該題對(duì)時(shí)間的要求很高，從上述代碼我們也能發(fā)現(xiàn)一些基本問(wèn)題，如BFS遍歷時(shí)可以構(gòu)建MAP，而不用單獨(dú)構(gòu)建MAP，非常耗時(shí)。其次，最關(guān)鍵的問(wèn)題在于DFS，此版本的DFS沒(méi)有進(jìn)行剪枝處理，剪枝能省去很多時(shí)間，所以我還需要對(duì)BFS進(jìn)行改進(jìn)。

思路：
首先，我們來(lái)看看上述代碼構(gòu)建圖的一個(gè)模型，如下圖所示：

很明顯，如果我們對(duì)BFS沒(méi)有做任何限制，我們拿到的鄰接表一定是上述探頭斯，而此時(shí)如果用DFS進(jìn)行搜索時(shí)，如從“hot”開(kāi)始，它會(huì)搜索：

一條可能的搜索路徑： hot ---> dot ---> dog ---> cog 但與此同時(shí)DFS還會(huì)搜索路徑： hot ---> dot ---> tot ---> hot 上述路徑很明顯不需要DFS，但因?yàn)檫叺南噙B，使得這種沒(méi)必要的搜索也將繼續(xù)。

所以一個(gè)優(yōu)化點(diǎn)就在于，好馬不吃回頭草，存在環(huán)路的回頭草絕對(duì)不是達(dá)到endWord的最短路徑。很遺憾，鄰接表無(wú)法表示這種非環(huán)的圖，所以想法就是用一個(gè)Map<String,Integer>來(lái)記錄到達(dá)每個(gè)單詞的最短路徑，一旦map中有該單詞，就不再更新最短路徑（避免環(huán)路搜索）

所以BFS代碼如下：

private int bfs(String beginWord, String endWord, Set<String> wordDict, Map<String, Integer> distanceMap,Map<String, List<String>> map) {if (!wordDict.contains(endWord))return 0;map.put(beginWord, new ArrayList<>());for (String word : wordDict) {map.put(word, new ArrayList<>());}Queue<String> queue = new LinkedList<>();queue.offer(beginWord);distanceMap.put(beginWord, 1);while (!queue.isEmpty()) {int count = queue.size();boolean foundEnd = false;// 這種循環(huán)遍歷很有意思，看作一個(gè)整體for (int i = 0; i < count; i++) {String cur = queue.poll();int curDistance = distanceMap.get(cur);List<String> neighbors = getNeighbors(cur, wordDict);if (neighbors.size() == 0)return 0;for (String neighbor : neighbors) {map.get(cur).add(neighbor);//存在環(huán)的情況，不去更新最短路徑if (!distanceMap.containsKey(neighbor)) {distanceMap.put(neighbor, curDistance + 1);if (endWord.equals(neighbor)) {foundEnd = true;} else {queue.offer(neighbor);}}}}//一旦抵到了endWord，我們就放棄建立后續(xù)的圖if (foundEnd)break;}return distanceMap.get(endWord);}

上述代碼在BFS時(shí)，與endWord無(wú)關(guān)的那些結(jié)點(diǎn)都丟棄掉了，且解決了有環(huán)路的情況。圖結(jié)構(gòu)如下所示：

這樣在DFS構(gòu)建路徑時(shí)，它的速度就比原先要快得多。在BFS中還需要注意一個(gè)函數(shù)【getNeighbors()】，剛開(kāi)始我寫(xiě)的這版程序也超時(shí)了，苦思許久都找不到原因，后來(lái)才發(fā)現(xiàn)是getNeighbors的玄機(jī)，它在建立鄰接表時(shí)，一定要使用【HashSet】的搜索方法，而不要用原生的【List】的搜索方法。

所以完整代碼如下：

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {Map<String, List<String>> map = new HashMap<>();Map<String, Integer> distanceMap = new HashMap<>();Set<String> wordDict = new HashSet<>(wordList);wordDict.add(beginWord);int distance = bfs(beginWord, endWord, wordDict, distanceMap, map);List<List<String>> ans = new ArrayList<>();if (distance == 0)return ans;dfs(map, beginWord, endWord, ans, new ArrayList<>(), distance, distanceMap);return ans;}private void dfs(Map<String, List<String>> map, String beginWord, String endWord, List<List<String>> ans,List<String> path, int distance, Map<String, Integer> distanceMap) {path.add(beginWord);if (distance == 0) {path.remove(path.size() - 1);return;}if (beginWord.equals(endWord)) {ans.add(new ArrayList<>(path));path.remove(path.size() - 1);return;}for (String find : map.get(beginWord)) {if (!distanceMap.containsKey(find))continue;if (distanceMap.get(beginWord) + 1 == distanceMap.get(find))dfs(map, find, endWord, ans, path, distance - 1, distanceMap);}path.remove(path.size() - 1);}private int bfs(String beginWord, String endWord, Set<String> wordDict, Map<String, Integer> distanceMap,Map<String, List<String>> map) {if (!wordDict.contains(endWord))return 0;map.put(beginWord, new ArrayList<>());for (String word : wordDict) {map.put(word, new ArrayList<>());}Queue<String> queue = new LinkedList<>();queue.offer(beginWord);distanceMap.put(beginWord, 1);while (!queue.isEmpty()) {int count = queue.size();boolean foundEnd = false;for (int i = 0; i < count; i++) {String cur = queue.poll();int curDistance = distanceMap.get(cur);List<String> neighbors = getNeighbors(cur, wordDict);if (neighbors.size() == 0)return 0;for (String neighbor : neighbors) {map.get(cur).add(neighbor);if (!distanceMap.containsKey(neighbor)) {distanceMap.put(neighbor, curDistance + 1);if (endWord.equals(neighbor)) {foundEnd = true;} else {queue.offer(neighbor);}}}}if (foundEnd)break;}return distanceMap.get(endWord);}private List<String> getNeighbors(String word, Set<String> wordList) {List<String> ans = new ArrayList<>();for (int i = 0; i < word.length(); i++) {char[] cc = word.toCharArray();for (char c = 'a'; c <= 'z'; c++) {cc[i] = c;String newWord = new String(cc);if (wordList.contains(newWord)) {if (newWord.equals(word))continue;ans.add(newWord);}}}return ans;}

DFS是一個(gè)典型的回溯+剪枝的遞歸方法，凡是函數(shù)返回的地方，我們都需要進(jìn)行狀態(tài)還原，注意再注意。

總結(jié)

以上是生活随笔為你收集整理的算法细节系列（20）：Word Ladder系列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。