leeyupeng

leeyupeng@126.com

0%

leetcode.127.单词接龙

发表于 更新于 分类于 ， 阅读次数： Valine：

单词接龙

问题描述

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

  • 1.每次转换只能改变一个字母。
  • 2.转换过程中的中间单词必须是字典中的单词。

说明:

  • 1.如果不存在这样的转换序列，返回 0。
  • 2.所有单词具有相同的长度。
  • 3.所有单词只由小写字母组成。
  • 4.字典中不存在重复的单词。
  • 5.你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

BFS

思路分析

BFS

代码实现

1
2


最短路径Dijkstra算法

思路分析

Dijkstra算法

代码实现

二维数组 结构方式 

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
class Solution {
public:
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
		wordList.insert(wordList.begin(),beginWord);

		int n = wordList.size();
		if (n > 10000)
		{
			return n;
		}
		int length = beginWord.length();
		vector<vector<bool>> matrix(n);
		int count = 0;

		int start = 0;
		int end = 0;
		for (int i = 0; i < n; i++)
		{
			matrix[i].insert(matrix[i].begin(), n, 0);
			if (wordList[i] == endWord) { end = i; }
		}
		if (end == 0)
		{
			return 0;
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = i + 1; j < n; j++)
			{
				count = 0;
				for (int l = 0; l < length; l++)
				{					
					if (wordList[i][l] != wordList[j][l])
					{
						count++;
						if (count > 1) { break; }
					}
				}
				if (count == 1) { matrix[i][j] = true; matrix[j][i] = true; }
			}
		}

		vector<int> distance(n);
		vector<int> prenode(n);
		//vector<bool> visited(n);
		set<int> s;
		for (int i = 0; i < n; i++) { s.insert(i); }
		int cur = 0;

		int mindistance;
		int next;
		s.erase(s.find(cur));
		int i;
		while (true)
		{
			mindistance = 0;
			next = 0;
			for(set<int>::iterator it = s.begin();it!=s.end();it++)
			{
				i = (*it);

				{
					if (matrix[cur][i] == true && (distance[i] == 0 || distance[i] > distance[cur] + 1))
					{
						distance[i] = distance[cur] + 1;
						prenode[i] = cur;
					}

					if (distance[i] != 0 && (mindistance == 0 || mindistance > distance[i]))
					{
						mindistance = distance[i];
						next = i;
					}
				}
			}
			cur = next;
			if (cur == 0)
			{
				break;
				break;
			}
			//visited[cur] = true;
			s.erase(s.find(cur));
			if (cur == end)
			{
				break;
			}
		}

		int ans = 0;
		if (cur == end)
		{
			ans = distance[end]+1;
		}
		return ans;
	}
};

代码实现

优化 

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
class Solution {
public:
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
		wordList.insert(wordList.begin(),beginWord);

		int n = wordList.size();
		int length = beginWord.length();
		int count = 0;

		vector<int> distance(n);
		set<int> s;
		for (int i = 0; i < n; i++) { s.insert(i); }
		int cur = 0;

		int mindistance;
		int next;
		s.erase(s.find(cur));
		int i;
		while (true)
		{
			mindistance = 0;
			next = 0;
			for(set<int>::iterator it = s.begin();it!=s.end();it++)
			{
				i = (*it);

				count = 0;
				for (int l = 0; l < length; l++)
				{
					if (wordList[cur][l] != wordList[i][l])
					{
						count++;
						if (count > 1) { break; }
					}
				}
				if (count == 1) {
					if (distance[i] == 0 || distance[i] > distance[cur] + 1)
					{
						distance[i] = distance[cur] + 1;
					}
				}

				{
					if (distance[i] != 0 && (mindistance == 0 || mindistance > distance[i]))
					{
						mindistance = distance[i];
						next = i;
					}
				}
			}
			cur = next;
			if (cur == 0)
			{
				break;
			}
			s.erase(s.find(cur));
			if (wordList[cur] == endWord)
			{
				break;
			}
		}

		int ans = 0;
		if (cur != 0)
		{
			ans = distance[cur] + 1;
		}
		return ans;
	}
};

最短路径AStar算法

思路分析

AStar算法

代码实现

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
class Solution {
public:
	///自定义优先级
	struct open {    ///不允许起名为 cmp ？
		int index;
		int distance;
		open(int i,int d)
		{
			index = i;
			distance = d;
		}
		bool operator < (const open &a) const{
			return distance > a.distance;///从小到大，最小值优先。
		}
	};
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
		wordList.insert(wordList.begin(),beginWord);

		int n = wordList.size();
		int length = beginWord.length();
		int count = 0;
		int count2 = 0;

		vector<int> distance(n);
		priority_queue<open> openDistance;
		vector<int> gDistance(n);

		set<int> s;
		int end = 0;
		for (int i = 0; i < n; i++) { s.insert(i); if (wordList[i] == endWord)end = i; }
		if (end == 0) { return 0; }
		int cur = 0;

		openDistance.push({0,0});

		int i;

		int ans = 0;
		while (!openDistance.empty())
		{
			if (s.find(openDistance.top().index) == s.end()) { openDistance.pop(); continue; }
			open o = openDistance.top();
			openDistance.pop();
			s.erase(s.find(o.index));

			cur = o.index;
			if (cur == end) {
				ans = o.distance + 1; break;
			}

			for(set<int>::iterator it = s.begin();it!=s.end();it++)
			{
				i = (*it);

				count = 0;
				for (int l = 0; l < length; l++)
				{
					if (wordList[cur][l] != wordList[i][l])
					{
						count++;
						if (count > 1) { break; }
					}
				}
				if (count == 1) {
					if (distance[i] == 0)
					{
						count2 = 0;
						for (int l = 0; l < length; l++)
						{
							if (wordList[i][l] != wordList[end][l])
							{
								count2++;
							}
						}

						gDistance[i] = count2;

						distance[i] = distance[cur] + 1;
						openDistance.push({i,distance[i] + gDistance[i]});
					}
					else if(distance[i] > distance[cur] + 1)
					{
						distance[i] = distance[cur] + 1;
						openDistance.push({ i,distance[i] + gDistance[i] });
					}
				}
			}
		}
		return ans;
	}
};