leetcode-word-ladder-ii

发表于   |   分类于 ，   |  

题目大意

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

　　接着上一篇博客的问题

题目分析

　　word-ladder-ii要求输出全部路径，要点如下：

  1. 主体思想还是BFS，但是要遍历到所有的最短路径情况，因此除了借助队列，还要存访问过的路径，也就是一张隐式图
  2. 对于标记数组的处理也有所不同，访问过一个字符串以后，不能直接标记为已访问，要等同层其它字符串也访问完以后，统一将这一层的字符串标记为已访问，否则上一层的其他尚未访问过的字符串再也访问不了这些字符串了。
  3. 在将字符串加入队列时，如果已经在同层访问过了，不要再加入队列，否则会重复。
  4. 最后对于记录的隐式图进行DFS

代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
public class Solution {
    private static List<List<String>> ans;
    private static String[] path; //记录DFS访问路径
    private static void dfs(String cur, String beginWord, Map<String, List<String>> parent, int idx) {
        path[idx] = cur;
		if (cur.equals(beginWord)) {
		    List<String> tmp = new ArrayList<String>();
		    for (int i = idx; i >= 0; i--) {
		        tmp.add(path[i]);
		    }
		    ans.add(tmp);
		    return;
		}
		List<String> list = parent.get(cur);
		for (String str : list) {
		    dfs(str, beginWord, parent, idx + 1);
		}
	}
	public static List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
		ans = new ArrayList<List<String>>();
		path = new String[wordList.size() + 1];
		Queue<String> queue = new LinkedList<String>(); //BFS 队列
		Map<String, List<String>> parent = new HashMap<String, List<String>>();//key是字符串，value是它的所有父节点
		queue.add(beginWord);
		queue.add(null);
		parent.put(beginWord, new ArrayList<String>()); 
		Set<String> v = new HashSet<String>(); //标记是否已访问过
		v.add(beginWord);
		boolean found = false;
		Set<String> level = new HashSet<String>(); // 缓存同层字符串
		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)) {
							found = true; // 标记为找到
							if (!parent.containsKey(cur)) {
							    List<String> tmp = new ArrayList<String>();
							    tmp.add(str);
							    parent.put(cur, tmp);
							} else {
							    List<String> tmp = parent.get(cur);
							    tmp.add(str);
							}
							continue;
						}
						if (!v.contains(cur)  && wordList.contains(cur)) {
							if (!level.contains(cur)) { //防止重复加入队列
								queue.add(cur);
								level.add(cur);
							}
							if (!parent.containsKey(cur)) { //不管重复与否，都要加入parent，因为一个字符串可以有多个父节点，比如"rex" "ted"都是"tex"的父节点
							    List<String> tmp = new ArrayList<String>();
							    tmp.add(str);
							    parent.put(cur, tmp);
							} else {
							    List<String> tmp = parent.get(cur);
							    tmp.add(str);
							}
						}
					}
				}
			} else {
				if (found) { //找到的那层全部遍历完了，证明已经找到最短路径了，直接dfs求解
				    dfs(endWord, beginWord, parent, 0);
				    break;
				}
				v.addAll(level); //统一将刚刚访问过的那一层整体标记为已访问
				level.clear();
				if (!queue.isEmpty()) {
					queue.add(null);
				}
			}
		}
		return ans;
	}
}

　　时间复杂度待分析。。