[LeetCode]Word Ladder，解题报告

目录题目

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a timeEach intermediate word must exist in the dictionary

For example,

Given: start = “hit” end = “cog” dict = [“hot”,”dot”,”dog”,”lot”,”log”] As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5.

Note:

思路

这道题目本身不难，但是很考察每个做题人的抽象能力。因为之前我在《编程之美》上看到过这个题目，所以我很快的能把这道题跟多叉树联系在一起。

我们假设start字符串为多叉树的根节点，end字符串为多叉树最后的叶子节点。那当start字符串改变其中一个字符形成的新字符串new，并且new属于dict字典当中，那new字符串就是start的第一个子节点。其他节点以此类推。

当我们把这道题目想成一个多叉树之后，接下来我们要做的就是从根节点开始，找一条能走到end节点的路径。遍历的方法有：BFS和DFS，从时间角度考虑，我们当然选择BFS。

AC代码

有人在明白了抽象成多叉树之后，依然可能面临TLE的问题。

原因：通常我们入队列的方式是从dict字典里选一个字符串，，判断和当前字符串是否相差一个字符，是则入队列，不是，则不入队列。这样的时间复杂度是O(n)，n是字典的数量。当n很大时，就容易TLE。

解决方案：我们可以换一种思路，英文字母一共26个，当前字符串的长度是L，所以我们用26个英文字母对当前字符串的每个字符挨个替换，看形成的新字符串是否在字典中。是则入队列，不是则不入队列。这样的时间复杂度是：O（L* 26）。这样亲测，不超时。

public class Solution {ladderLength(String start, String end, Set<String> dict) {int dist = calDistance(start, end);if (dist == 1) {return 2;}return bfsDict(dict, start, end);}calDistance(String word1, String word2) {int dist = 0;for (int i = 0; i < word1.length(); i++) {if (word1.charAt(i) != word2.charAt(i)) {dist += 1;}}return dist;}enQueue(Set<String> dict, LinkedList<String> queue, String target, Map<String, Integer> map, int step) {if (dict == null || dict.isEmpty()) {return;}for (int i = 0; i < target.length(); i++) {for (char c = ‘a’; c <= ‘z’; c++) {StringBuilder sBuilder = new StringBuilder(target);if (sBuilder.charAt(i) == c) {continue;}sBuilder.setCharAt(i, c);if (dict.contains(sBuilder.toString())) {queue.addLast(sBuilder.toString());dict.remove(sBuilder.toString());map.put(sBuilder.toString(), step + 1);}}}}bfsDict(Set<String> dict, String start, String end) {LinkedList<String> queue = new LinkedList<String>();Map<String, Integer> hashMap = new HashMap<String, Integer>();enQueue(dict, queue, start, hashMap, 1);while (!queue.isEmpty()) {String word = queue.poll();int step = hashMap.get(word);if (calDistance(word, end) == 1) {return step + 1;}enQueue(dict, queue, word, hashMap, step);}return 0;}}

如果心在远方，只需勇敢前行，梦想自会引路，