Word Ladder @LeetCode

这道题 采用BFS来解答。 每一层的结果入队，下一层再遍历每一个可能的所有的可能。 层层遍历，某层找到结果就可以直接返回，比起DFS 会更快！
写之前都是满头雾水，写完后 就发现无比优美 哈哈！
解题报告：
最直观的思路就是DFS，每次变成新的单词，同时从字典中删除新单词然后不断递归。
大数据时候超时。可以使用BFS，求出每次改变一个字母后在字典中存在的单词。之后逐层便利，和DFS不一样不一次走到最深。
思考一下DFS和BFS的区别，举个最简单的例子，111 -> 311。 
DFS的话，111->112，之后需要DFS 112的所有变形。同理111->113之后还要遍历113的所有变形。
而BFS的话，111->112 113 121 131 211 311只需要6次就能找到最终结果。

ref: http://www.qnwz.net/kaifa/166667.html 答案是参考九章算法解题站的，超级优美： http://answer.ninechapter.com/solutions/word-ladder/

public class Solution {public int ladderLength(String start, String end, Setdict) {if (dict == null || dict.size() == 0) {return 0;}HashSetdictH = new HashSet(dict);Queueq = new LinkedList(); q.offer(start); dictH.remove(start); int len = 1; // q存放的是本层所有可能的string。例如111-> (112, 113, 131, 311)，也就是说本层所有的变换 while (!q.isEmpty()) { int cnt = q.size(); for (int i = 0; i < cnt; i++) { // 取出队列中的每一个string,对它的所有的可能的变换进行一次bfs。 String s = q.poll(); // 某个string的每一个字符的每一个变换都要遍历. for (int j = 0; j < s.length(); j++) { for (char c = 'a'; c <= 'z'; c++) { if (c == s.charAt(j)) { // 不需要遍历它本身 continue; } String tmp = replace(s, j, c); if (tmp.equals(end)) { // 逐次遍历 在某层找到解就可以直接退出 return len + 1; } // 如果不是解，就先加入队列 ，准备下一层的遍历。 if (dictH.contains(tmp)) { dictH.remove(tmp); q.offer(tmp); } } } } len++; } return 0; } // replace the char in p to be c. public String replace(String s, int p, char c) { StringBuilder sb = new StringBuilder(s); sb.setCharAt(p, c); return sb.toString(); } } 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！