Joyce' Blog
0%

word-ladder-ii

发表于 更新于

题目描述

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：

  1. 每次转换只能改变一个字母。

  2. 转换过程中的中间单词必须是字典中的单词。

说明:

  • 如果不存在这样的转换序列，返回一个空列表。

  • 所有单词具有相同的长度。

  • 所有单词只由小写字母组成。
  • 字典中不存在重复的单词。
  • 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

题解

想法：转化为图，单词做为顶点，相差一个字母的两个单词之间连一条边，问题转化为：求两个点之间所有的最短路径。

原始的Dijkstra算法得到的是从源点到其他点的一条最短路径，即 一颗最短路径树。在这里，对Dijkstra算法进行修正，得到一个最短路径图，使得从源点到指定点的人一两条路径都具有相同的距离。基于最短路径图，应用Yin算法罗列从源点到指定点的所有最短路径。

修正后的Dijkstra算法

$T$表示从源点$v_1$到$v$的最短路径的上限，记为$T(v)$，$P$表示从原点$v_1$到这一点的最短路径，集合$S$表示所有具有$P$的点的集合。函数$\lambda(v)$表示路径$R$中点$v$的上一个点。

  1. 初始化：$T(v_1)=0，\mu(y,x)=0，R={v_1}，S=\phi$
  2. 在集合$R$中选取具有最小$T$标号的点$y$，则：$S=S\bigcup{y}, R=R-{y}$；若边$(y,x)\in E$且$x\notin S$，则$R=R\bigcup{x}$
  3. 若边$(y,x)\in E$，则：若$T(y)+w(y,x)<T(x)$，则$T(x)=T(y)+w(y,x), \mu(y,x)=1$，同时若$\mu(z,x)=1$且$z\neq y$，则$ \mu(z,x)=0$；若$T(y)+w(y,x) = T(x)$，则$\mu(y,x)=1$。
  4. 如果所有点进入集合$S$，那么算法停止，把所有$\mu(y,x)=0$的边从图$G(V,E)$中删去，得到的新图就是最短路径图。否则，转到step2.

算法思想：根据各最短路径中边的数目对各最短路径进行排序，变数越少的最短路径对应的级别就越高，算法按照由高到低的顺序依次列出所有的最短路径。在这道题中，各边的权均为1，那么从源点到指定点的路径长度越短，该路径的级别就越高，按照级别由高到低依次列出所有的最短路径，可以借助于求第$k$条最短路径问题的Yen算法来解决。

Yen算法的思想是,首先求得从源点到指定点的第1,2,…,k-1条最短路径,然后在这k-1条最短路径的基础上求得第k条最短路径.由于在最短路径图中,从源点到指定点的最短路径是有限的,因而当k足够大时,按照Yen算法总可以求得从源点到指定点的所有最短路径.

test

参考文献
https://wenku.baidu.com/view/0254244b001ca300a6c30c22590102020740f2d8.html
王志坚，韩伟一，李一军. 具有多条最短路径的最短路问题[J]. 哈尔滨工业大学学报，2010，42（9）：1429-1431.

Anyway, wrong again. Debug tomorrow and learn parallel slide.

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#define INF 200000000
#define N 1000

struct Edge
{
	int to;          // 边终止节点
	int cost;        // 花费

	Edge(int to1, int cost1)
	{
		to = to1;
		cost = cost1;
	}
};

int nV;                      // 顶点数
vector<Edge> G[N];           // 图的邻接表形式
int dist[N];                 // 从源点出发的最短距离
typedef pair<int, int> P;    // first是最短距离，second是顶点编号
bool vis[N];
vector<Edge> G4[N];
int G1[N][N];                // 图的邻接矩阵形式

void addEdge(int from, int to, int cost, vector<Edge> G[N])
{
	Edge e(to, cost);
	G[from].push_back(e);

	Edge e1(from, cost);
	G[to].push_back(e1);
}

void dijkstra(int s, vector<Edge> G[N])
{
	fill(dist, dist + nV + 1, INF);
	priority_queue<P, vector<P>, greater<P> > q;
	dist[s] = 0;
	q.push(P(0, s));
	while (!q.empty())
	{
		P p = q.top();   //从尚未使用的顶点中找到一个距离最小的顶点
		q.pop();
		int v = p.second;
		if (dist[v] < p.first)
			continue;
		for (int i = 0; i<G[v].size(); i++)
		{
			Edge &e = G[v][i];
			int dis = dist[v] + e.cost;
			if (dist[e.to] > dis)
			{
				dist[e.to] = dist[v] + e.cost;
				q.push(P(dist[e.to], e.to));
				G4[v].push_back(e);
			}
			else if (dist[e.to] == dis)
			{
				G4[v].push_back(e);
			}
		}
	}
}

struct Ans
{
	vector<int> link;
	int cost;
	int start;

	void getCost()
	{
		cost = G1[start][link[0]];
		for (int i = 0; i<link.size() - 1; i++)
		{
			cost += G1[link[i]][link[i + 1]];
		}
	}
};

void dfs(int s, int t, Ans &A, vector< Ans > &paths, int start)
{
	if (s == t)
	{
		A.start = start;
		A.getCost();
		paths.push_back(A);
	}

	for (int i = 0; i < G4[s].size(); i++)
	{
		int u = G4[s][i].to;
		if (!vis[u])
		{
			vis[u] = true;
			A.link.push_back(u);
			dfs(u, t, A, paths, start);
			A.link.pop_back();
			vis[u] = false;
		}
	}
}

bool neighbour(string s1, string s2)
{
	bool flag = true;
	int i = 0;
	//所有单词具有相同的长度
	while (i < s1.length())
	{
		if (s1[i] != s2[i])
		{
			if (flag)
				flag = false;
			else
				return false;
		}
		i++;
	}
	return true;
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) 
{
	//beginWord 和 endWord 是非空的，且二者不相同
	int source = 0;
	int vsize = wordList.size();
	for (; source < vsize; source++)
	{
		if (wordList[source] == beginWord)break;
	}
	if (source == vsize)
	{
		wordList.push_back(beginWord);
		vsize++;
	}
	
	int destination = 0;
	for (; destination < vsize; destination++)
	{
		if (wordList[destination] == endWord)break;
	}
	if (destination == vsize)return {};
	nV = vsize;

	//这里假设beginWord 和 endWord不在wordList中	

	//build graph
	for (int i = 0; i<vsize; i++)
	{
		for (int j = i; j<vsize; j++)
		{
			G1[i][j] = G1[j][i] = INF;
		}
	}
	for (int i = 0; i < vsize; i++)
	{
		for (int j = i + 1; j < vsize; j++)
		{
			if (neighbour(wordList[i], wordList[j]))
			{
				addEdge(i, j, 1, G);
				G1[i][j] = G1[j][i] = 1;
			}
		}
	}
	
	//get new graph
	dijkstra(source, G);

	//Yen算法
	vector<vector<string>> res;
	vector<Ans> paths;
	Ans ans;
	memset(vis, false, sizeof(vis));
	dfs(source, destination, ans, paths, 1);

	for (int i = 0; i<paths.size(); i++)
	{
		vector<string> tmp = { beginWord };
		for (int j = 0; j<paths[i].link.size(); j++)
		{
			tmp.push_back(wordList[paths[i].link[j]]);
		}
		res.push_back(tmp);
	}
	return res;
}
int singleNumber(vector<int>& nums) {
	int res = 0;
	for (int i = 0; i<nums.size(); i++)
		res ^= nums[i];
	return res;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
	unordered_set<string> dict(wordList.begin(), wordList.end());
	if (dict.find(endWord) == dict.end()) return 0;
	// 初始化起始和终点
	unordered_set<string> beginSet, endSet, tmp, visited;
	beginSet.insert(beginWord);
	endSet.insert(endWord);
	int len = 1;

	while (!beginSet.empty() && !endSet.empty()) {
		if (beginSet.size() > endSet.size()) {
			tmp = beginSet;
			beginSet = endSet;
			endSet = tmp;
		}
		tmp.clear();
		for (string word : beginSet) {
			for (int i = 0; i < word.size(); i++) {
				char old = word[i];
				for (char c = 'a'; c <= 'z'; c++) {
					if (old == c) continue;
					word[i] = c;
					if (endSet.find(word) != endSet.end()) {
						return len + 1;
					}
					if (visited.find(word) == visited.end() && dict.find(word) != dict.end()) {
						tmp.insert(word);
						visited.insert(word);
					}
				}
				word[i] = old;
			}
		}
		beginSet = tmp;
		len++;
	}
	return 0;
}

这就很过分了，vs和leetcode里面运行出来的结果居然不一样。

大佬的看着就很简洁。使用标准的BFS遍历，将已经访问过的单词加入待删除集合dels中，不要立即删除。因为在同一层遍历时，有可能有多种路径，即多个解。这是与127的区别之一。
使用trace记住当前单词的前驱，注意前驱有多个（即有可能多个解），然后使用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
// Time 156ms, Space 22MB
class Solution {
	void dfs(unordered_map<string,unordered_set<string> > &trace, const string &last, vector<string> path, vector<vector<string> > &vs){
		path.push_back(last);
		if(trace.count(last)==0){
			reverse(path.begin(),path.end());
			vs.push_back(path);
			return;
		}
		for(const string &word:trace[last])
			dfs(trace,word,path,vs);
	}
public:
	vector<vector<string>> findLadders(string begin, string end, vector<string>& wordList) {
		unordered_set<string> dict(wordList.begin(),wordList.end());
		if (dict.count(end)==0) return {};
		unordered_map<string,unordered_set<string> > trace;
		unordered_set<string> q={begin}, dels;
		for(; q.size() && trace.count(end)==0; q=dels){
			for(const string &word:q)
				dict.erase(word);
			dels.clear();
			for(const string &word:q){
				for(int i=0; i<word.length(); ++i){
					string s=word;
					for(char ch='a'; ch<='z'; ++ch){
						if(word[i]==ch) continue;
						s[i] = ch;
						if(dict.find(s)==dict.end()) continue;
						trace[s].insert(word);
						dels.insert(s);
					}
				}
			}
		}
		if(trace.size()==0) return {};
		vector<vector<string> > result;
		dfs(trace,end,{},result);
		return result;
	}
};

作者：joy-teng
链接：https://leetcode-cn.com/problems/word-ladder-ii/solution/bfsdfs-by-joy-teng/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。