如何求解LeetCode 126. Word Ladder II的单词接龙问题？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1712个文字，预计阅读时间需要7分钟。
我们可以将起始字符串、终止字符串以及单词表中的所有字符串组合成新的字符串，然后找出这些字符串中重复出现的最小次数。如果两个字符串只有一个字符不同，则它们被认为是连续的。为了找到最小的修改次数，我们将尝试将每个字符串与单词表中的其他字符串进行匹配，并计算所需的修改次数。以下是实现这一功能的步骤：
1. 定义起始字符串、终止字符串和单词表。
2.创建一个函数来计算两个字符串之间的编辑距离（修改次数）。
3.遍历单词表，计算每个字符串与起始字符串和终止字符串的编辑距离。
4.对于每个字符串，记录其与起始字符串和终止字符串的最小编辑距离。
5.输出具有最小编辑距离的字符串及其对应的修改次数。
python
def edit_distance(str1, str2): if len(str1)if len(str2)==0: return len(str1)
previous_row=range(len(str2) + 1) for i, c1 in enumerate(str1): current_row=[i + 1] for j, c2 in enumerate(str2): insertions=previous_row[j + 1] + 1 deletions=current_row[j] + 1 substitutions=previous_row[j] + (c1 !=c2) current_row.append(min(insertions, deletions, substitutions)) previous_row=current_row
return previous_row[-1]
定义起始字符串、终止字符串和单词表start_str=startend_str=endword_list=[example, sample, end, start, test]
计算并输出结果min_distance=float('inf')min_distance_str=None
for word in word_list: distance_start=edit_distance(start_str, word) distance_end=edit_distance(end_str, word) min_distance=min(min_distance, distance_start, distance_end) if min_distance==distance_start or min_distance==distance_end: min_distance_str=word
print(fThe string with the minimum edit distance is: '{min_distance_str}' with a distance of {min_distance}.)
这段代码将输出具有最小编辑距离的字符串及其对应的修改次数。
我们可以把起始字符串、终止字符串、以及单词表里所有的字符串想象成节点。若两个字符串只有一个字符不同，那它们相连。因为题目需要输出个性次数最少的所有修改方式，因此我们可以使用广度优先搜索，求得起始节点到终止节点的最短距离。 一、题目大意标签: 搜索
leetcode.cn/problems/word-ladder-ii
按字典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] 的形式返回。
示例 1：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
示例 2：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：[]
解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。
提示：
- 1 <= beginWord.length <= 5
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- wordList[i].length == beginWord.length
- beginWord、endWord 和 wordList[i] 由小写英文字母组成
- beginWord != endWord
- wordList 中的所有单词 互不相同
我们可以把起始字符串、终止字符串、以及单词表里所有的字符串想象成节点。若两个字符串只有一个字符不同，那它们相连。因为题目需要输出个性次数最少的所有修改方式，因此我们可以使用广度优先搜索，求得起始节点到终止节点的最短距离。
一个小技巧：我们燕不是直接从起始节点进行广度优先搜索，直到找到终止节点为止，而是从起始节点和终止节点分别进行广度优先搜索，每次只延展当前层节点数最少的那一端，这样我们可以减少搜索的总结点数。举例来说，假设最短距离为4，如果我们只从一端搜索4层，总遍历节点数最多是 1+2+4+8+16=31，如果我们从两端各搜索2层，总遍历节点数最多为2 * (1+2+4)=14。
搜索结束后，我们还需要通过回溯法来重建所有可能的路径。
public class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> ans = new ArrayList<>();
// 优化
Set<String> dict = new HashSet<>(wordList);
// for (String w : wordList) {
// dict.add(w);
// }
if (!dict.contains(endWord)) {
return ans;
}
dict.remove(beginWord);
dict.remove(endWord);
Set<String> q1 = new HashSet<>();
q1.add(beginWord);
Set<String> q2 = new HashSet<>();
q2.add(endWord);
Map<String, List<String>> next = new HashMap<>();
boolean reversed = false;
boolean found = false;
while (!q1.isEmpty()) {
Set<String> q = new HashSet<>();
for (String w : q1) {
String s = w;
for (int i = 0; i < s.length(); i++) {
char[] sArr = s.toCharArray();
char ch = sArr[i];
for (int j = 0; j < 26; j++) {
sArr[i] = (char) (j + 'a');
s = String.valueOf(sArr);
if (q2.contains(s)) {
if (reversed) {
add(next, s, w);
} else {
add(next, w, s);
}
found = true;
}
if (dict.contains(s)) {
if (reversed) {
add(next, s, w);
} else {
add(next, w, s);
}
q.add(s);
}
}
sArr[i] = ch;
s = String.valueOf(sArr);
}
}
if (found) {
break;
}
for (String w : q) {
dict.remove(w);
}
if (q.size() <= q2.size()) {
q1 = q;
} else {
reversed = !reversed;
q1 = q2;
q2 = q;
}
}
if (found) {
Deque<String> path = new ArrayDeque<>();
path.add(beginWord);
backTracking(beginWord, endWord, next, path, ans);
}
return ans;
}
void backTracking(String src, String dst, Map<String, List<String>> next, Deque<String> path, List<List<String>> ans) {
if (src == dst) {
ans.add(new ArrayList<>(path));
return;
}
for (String s : next.get(src)) {
path.addLast(s);
backTracking(s, dst, next, path, ans);
path.removeLast();
}
}
private void add(Map<String, List<String>> map, String key, String value) {
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(value);
}
}
四、总结小记
- 2022/6/8 这道题烧脑子呀
本文共计1712个文字，预计阅读时间需要7分钟。
我们可以将起始字符串、终止字符串以及单词表中的所有字符串组合成新的字符串，然后找出这些字符串中重复出现的最小次数。如果两个字符串只有一个字符不同，则它们被认为是连续的。为了找到最小的修改次数，我们将尝试将每个字符串与单词表中的其他字符串进行匹配，并计算所需的修改次数。以下是实现这一功能的步骤：
1. 定义起始字符串、终止字符串和单词表。
2.创建一个函数来计算两个字符串之间的编辑距离（修改次数）。
3.遍历单词表，计算每个字符串与起始字符串和终止字符串的编辑距离。
4.对于每个字符串，记录其与起始字符串和终止字符串的最小编辑距离。
5.输出具有最小编辑距离的字符串及其对应的修改次数。
python
def edit_distance(str1, str2): if len(str1)if len(str2)==0: return len(str1)
previous_row=range(len(str2) + 1) for i, c1 in enumerate(str1): current_row=[i + 1] for j, c2 in enumerate(str2): insertions=previous_row[j + 1] + 1 deletions=current_row[j] + 1 substitutions=previous_row[j] + (c1 !=c2) current_row.append(min(insertions, deletions, substitutions)) previous_row=current_row
return previous_row[-1]
定义起始字符串、终止字符串和单词表start_str=startend_str=endword_list=[example, sample, end, start, test]
计算并输出结果min_distance=float('inf')min_distance_str=None
for word in word_list: distance_start=edit_distance(start_str, word) distance_end=edit_distance(end_str, word) min_distance=min(min_distance, distance_start, distance_end) if min_distance==distance_start or min_distance==distance_end: min_distance_str=word
print(fThe string with the minimum edit distance is: '{min_distance_str}' with a distance of {min_distance}.)
这段代码将输出具有最小编辑距离的字符串及其对应的修改次数。
我们可以把起始字符串、终止字符串、以及单词表里所有的字符串想象成节点。若两个字符串只有一个字符不同，那它们相连。因为题目需要输出个性次数最少的所有修改方式，因此我们可以使用广度优先搜索，求得起始节点到终止节点的最短距离。 一、题目大意标签: 搜索
leetcode.cn/problems/word-ladder-ii
按字典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] 的形式返回。
示例 1：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
示例 2：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：[]
解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。
提示：
- 1 <= beginWord.length <= 5
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- wordList[i].length == beginWord.length
- beginWord、endWord 和 wordList[i] 由小写英文字母组成
- beginWord != endWord
- wordList 中的所有单词 互不相同
我们可以把起始字符串、终止字符串、以及单词表里所有的字符串想象成节点。若两个字符串只有一个字符不同，那它们相连。因为题目需要输出个性次数最少的所有修改方式，因此我们可以使用广度优先搜索，求得起始节点到终止节点的最短距离。
一个小技巧：我们燕不是直接从起始节点进行广度优先搜索，直到找到终止节点为止，而是从起始节点和终止节点分别进行广度优先搜索，每次只延展当前层节点数最少的那一端，这样我们可以减少搜索的总结点数。举例来说，假设最短距离为4，如果我们只从一端搜索4层，总遍历节点数最多是 1+2+4+8+16=31，如果我们从两端各搜索2层，总遍历节点数最多为2 * (1+2+4)=14。
搜索结束后，我们还需要通过回溯法来重建所有可能的路径。
public class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> ans = new ArrayList<>();
// 优化
Set<String> dict = new HashSet<>(wordList);
// for (String w : wordList) {
// dict.add(w);
// }
if (!dict.contains(endWord)) {
return ans;
}
dict.remove(beginWord);
dict.remove(endWord);
Set<String> q1 = new HashSet<>();
q1.add(beginWord);
Set<String> q2 = new HashSet<>();
q2.add(endWord);
Map<String, List<String>> next = new HashMap<>();
boolean reversed = false;
boolean found = false;
while (!q1.isEmpty()) {
Set<String> q = new HashSet<>();
for (String w : q1) {
String s = w;
for (int i = 0; i < s.length(); i++) {
char[] sArr = s.toCharArray();
char ch = sArr[i];
for (int j = 0; j < 26; j++) {
sArr[i] = (char) (j + 'a');
s = String.valueOf(sArr);
if (q2.contains(s)) {
if (reversed) {
add(next, s, w);
} else {
add(next, w, s);
}
found = true;
}
if (dict.contains(s)) {
if (reversed) {
add(next, s, w);
} else {
add(next, w, s);
}
q.add(s);
}
}
sArr[i] = ch;
s = String.valueOf(sArr);
}
}
if (found) {
break;
}
for (String w : q) {
dict.remove(w);
}
if (q.size() <= q2.size()) {
q1 = q;
} else {
reversed = !reversed;
q1 = q2;
q2 = q;
}
}
if (found) {
Deque<String> path = new ArrayDeque<>();
path.add(beginWord);
backTracking(beginWord, endWord, next, path, ans);
}
return ans;
}
void backTracking(String src, String dst, Map<String, List<String>> next, Deque<String> path, List<List<String>> ans) {
if (src == dst) {
ans.add(new ArrayList<>(path));
return;
}
for (String s : next.get(src)) {
path.addLast(s);
backTracking(s, dst, next, path, ans);
path.removeLast();
}
}
private void add(Map<String, List<String>> map, String key, String value) {
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(value);
}
}
四、总结小记
- 2022/6/8 这道题烧脑子呀