leetcode-word-ladder

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/word-ladder/

　　给你一个起始字符串和终止字符串，和一个字符串数组，让你求出起始字符串和终止字符串的距离，距离上的路径上相邻字符串只有一个字符不相同，并且属于字符串数组的。

题目分析

　　这个题本质上类似图论上的最短路径，并要求路径上字符串的距离为1，但这么做直接TLE。要用BFS，思路参考了：https://discuss.leetcode.com/topic/17890/another-accepted-java-solution-bfs/ 但有几个坑的地方容易导致TLE：

  1. 不要用二维数组提前计算两两字符串距离，很多次计算是没有用的，因为两个字符串距离只会被计算一次。
  2. 计算字符串下一相邻节点时，最好不要遍历整个set取其中未访问的，而是应该根据字符串可能的下一层可能进行扩展，因为单个字符的可能一共就是26个。这么做每次生成下一层的复杂度是26 * 字符串长度，而如果遍历整个set生成下一层复杂度是set元素个数，当字符串平均长度远远小于set中元素个数时，效率差别有很明显。
  3. 直接就用Set的唯一性判断是否访问过就行，没有必要单独引入一个辅助数组标记访问过。
  4. 层数可以再开一个辅助队列，也可以按下面代码，在每一层的节点都放入队列以后，再push进入一个null，再出队时，如果是null，意味着上一层已经全部访问过了，该访问新的一层了，因此level++

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
    
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        Queue<String> queue = new LinkedList<String>();
        queue.add(beginWord);
        queue.add(null);
        Set<String> v = new HashSet<String>();
        v.add(beginWord);
        int level = 1;
        while (!queue.isEmpty()) {
            String str = queue.poll();
            if (str != null) {
                int len = str.length();
                for (int i = 0; i < len; i++) {
                    char[] chars = str.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[i] = c;
                        String cur = new String(chars);
                        if (cur.equals(endWord)) {
                            return level + 1;
                        }
                        if (!v.contains(cur) && wordList.contains(cur)) {
                            queue.add(cur);
                            v.add(cur);
                        }
                    }
                }
            } else {
                level++;
                if (!queue.isEmpty()) {
                    queue.add(null);
                }
            }
        }
        return 0;
    }
}