---

前言

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> … -> sk 这样的单词序列，并满足：

每对相邻的单词之间仅有单个字母不同。
转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
sk == endWord
给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, …, sk] 的形式返回。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/word-ladder-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

做出表里每一个字符串的邻接表， 生成map
key: abc
value:有哪些是abc改变-个字符就能到达的, 但前提得是这里面的每一个字符串在表里都有
重要限制,字符都是小写, a~z 26种，怎么样最快

第一步
我第一个字符变成bbc，第一个字符变成cbc第一个字符变成dbc第一个字符一直 变到zbc。
我看这些字符串在表里，谁有谁没有,有的都是我的邻居。

第二步:盯着第二字符变化，看aac, acc, a…azc在表里有没有
第三步:盯着第三字符
穷举了它的邻居的所有可能

如果你把abc拿出来，你剩下所有字符串跟它搞一遍，你什么代价?
你每一个字符串都得遍历一下你这个长度来确定是不是只有一个字符跟它不一样对吧，假设你字符串长度为K,
你剩下的字符串数量是N个，你每一个字符串都得遍历一 遍。只有一个位置的字符对不上，都得这么去试。
所以复杂度O (NK) 。
而a~ z小写字母替换这种方法,第一个位置有几种可能性? 26种, 第二个就集中可能性，26种, 第三个就几
种可能性26种。假设字符事长度为K,只需要尝试26k这么多字符串就够了，每一一个字符串去希表中查一下
这个代价O(K),所以复杂度0(26 * K²)
所以你可以在表中找到一个字符串跟表中剩下所有字符串搞一下O (N* K),
也可以用每个字符替换的方式O(K^2),选择用哪个?看看字符串更长还是N更长，看菜下饭,根据数据量
决定用哪一种

生成距离表BFS
距离表对start负责

生成距离表,在距离表中，我只走向那些距离为一的支路
我不是所有支路都走的，不走距离没有严格增加的支路

距离每次严格+1
距离表指导我的深度优先遍历

代码

public static int canCompleteCircuit(int[] gas, int[] cost) {
		if (gas == null || gas.length == 0) {
			return -1;
		}
		if (gas.length == 1) {
			return gas[0] < cost[0] ? -1 : 0;
		}
		boolean[] good = stations(cost, gas);
		for (int i = 0; i < gas.length; i++) {
			if (good[i]) {
				return i;
			}
		}
		return -1;
	}

	public static boolean[] stations(int[] cost, int[] gas) {
		if (cost == null || gas == null || cost.length < 2 || cost.length != gas.length) {
			return null;
		}
		int init = changeDisArrayGetInit(cost, gas);
		return init == -1 ? new boolean[cost.length] : enlargeArea(cost, init);
	}

	public static int changeDisArrayGetInit(int[] dis, int[] oil) {
		int init = -1;
		for (int i = 0; i < dis.length; i++) {
			dis[i] = oil[i] - dis[i];
			if (dis[i] >= 0) {
				init = i;
			}
		}
		return init;
	}

	public static boolean[] enlargeArea(int[] dis, int init) {
		boolean[] res = new boolean[dis.length];
		int start = init;
		int end = nextIndex(init, dis.length);
		int need = 0;
		int rest = 0;
		do {
			// 当前来到的start已经在连通区域中，可以确定后续的开始点一定无法转完一圈
			if (start != init && start == lastIndex(end, dis.length)) {
				break;
			}
			// 当前来到的start不在连通区域中，就扩充连通区域
			// start(5) ->  联通区的头部(7) -> 2
			// start(-2) -> 联通区的头部(7) -> 9
			if (dis[start] < need) { // 当前start无法接到连通区的头部
				need -= dis[start];
			} else { // 当前start可以接到连通区的头部，开始扩充连通区域的尾巴
				// start(7) -> 联通区的头部(5)
				rest += dis[start] - need;
				need = 0;
				while (rest >= 0 && end != start) {
					rest += dis[end];
					end = nextIndex(end, dis.length);
				}
				// 如果连通区域已经覆盖整个环，当前的start是良好出发点，进入2阶段
				if (rest >= 0) {
					res[start] = true;
					connectGood(dis, lastIndex(start, dis.length), init, res);
					break;
				}
			}
			start = lastIndex(start, dis.length);
		} while (start != init);
		return res;
	}

	// 已知start的next方向上有一个良好出发点
	// start如果可以达到这个良好出发点，那么从start出发一定可以转一圈
	public static void connectGood(int[] dis, int start, int init, boolean[] res) {
		int need = 0;
		while (start != init) {
			if (dis[start] < need) {
				need -= dis[start];
			} else {
				res[start] = true;
				need = 0;
			}
			start = lastIndex(start, dis.length);
		}
	}

	public static int lastIndex(int index, int size) {
		return index == 0 ? (size - 1) : index - 1;
	}

	public static int nextIndex(int index, int size) {
		return index == size - 1 ? 0 : (index + 1);
	}
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
84
85
86
87
88
89
90
91
92
93