class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
}
};
126. 单词接龙 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 <= 5endWord.length == beginWord.length1 <= wordList.length <= 500wordList[i].length == beginWord.lengthbeginWord、endWord 和 wordList[i] 由小写英文字母组成beginWord != endWordwordList 中的所有单词 互不相同相似题目
原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2.5 MB, 提交时间: 2023-09-23 11:00:00
func findLadders(beginWord string, endWord string, wordList []string) [][]string {
if !wordin(endWord, wordList) {
return nil
}
if dif(beginWord, endWord)==1 {
return [][]string{{beginWord, endWord}}
}
status := make([]int, len(wordList))
q := []int{}
k := 1
for i := 0; i < len(wordList); i++ {
if dif(wordList[i], beginWord) == 1{
q = append(q, i)
status[i] = k
}
}
var q1 []int
found := false
for len(q) > 0 && !found{
k++
for _, i := range q {
for j := range wordList {
if status[j] > 0 {
continue
}
if dif(wordList[i], wordList[j]) == 1 {
q1 = append(q1, j)
status[j] = k
if wordList[j] == endWord {
found = true
break
}
}
}
if found {
break
}
}
q, q1 = q1, q[:0]
}
if !found {
return nil
}
var res [][]string = [][]string{{endWord}}
var tmp [][]string
for i := k-1; i >=1; i-- {
for j :=0; j < len(status); j++ {
if status[j] == i {
for _, r := range res {
if dif(r[len(r)-1], wordList[j]) == 1 {
rs := make([]string, 0, len(r)+1)
rs = append(rs, r...)
rs = append(rs, wordList[j])
tmp = append(tmp, rs)
}
}
}
}
res, tmp = tmp, [][]string{}
}
for i := 0; i < len(res); i++ {
res[i] = revert(append(res[i], beginWord))
}
return res
}
func revert(ws []string) []string {
i, j :=0, len(ws)-1
for i < j {
ws[i], ws[j] = ws[j], ws[i]
i++
j--
}
return ws
}
func wordin(word string, wordList []string) bool {
for _, w := range wordList {
if w == word {
return true
}
}
return false
}
func dif(w1, w2 string) int {
k := 0
for i := 0; i < len(w1); i++ {
if w1[i] != w2[i] {
k++
if k > 1 {
return k
}
}
}
return k
}
python3 解法, 执行用时: 52 ms, 内存消耗: 16.5 MB, 提交时间: 2023-09-23 10:58:38
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
wordList.append(beginWord)
### 构建具有邻接关系的桶
buckets = defaultdict(list)
for word in wordList:
for i in range(len(beginWord)):
match = word[:i] + '_' + word[i+1:]
buckets[match].append(word)
##### BFS遍历
preWords = defaultdict(list) # 前溯词列表
toSeen = deque([(beginWord, 1)]) # 待遍历词及深度
beFound = {beginWord:1} # 已探测词列表
while toSeen:
curWord, level = toSeen.popleft()
for i in range(len(beginWord)):
match = curWord[:i] + '_' + curWord[i+1:]
for word in buckets[match]:
if word not in beFound:
beFound[word] = level+1
toSeen.append((word, level+1))
if beFound[word] == level+1: # 当前深度等于该词首次遍历深度，则仍应加入前溯词列表
preWords[word].append(curWord)
if endWord in beFound and level+1 > beFound[endWord]: # 已搜索到目标词，且完成当前层遍历
break
#### 列表推导式输出结果
if endWord in beFound:
res = [[endWord]]
while res[0][0] != beginWord:
res = [[word] + r for r in res for word in preWords[r[0]]]
return res
else:
return []
java 解法, 执行用时: 14 ms, 内存消耗: 43.6 MB, 提交时间: 2023-09-23 10:57:43
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> res = new ArrayList<>();
// 因为需要快速判断扩展出的单词是否在 wordList 里，因此需要将 wordList 存入哈希表，这里命名为「字典」
Set<String> dict = new HashSet<>(wordList);
// 特殊用例判断
if (!dict.contains(endWord)) {
return res;
}
dict.remove(beginWord);
// 第 1 步：广度优先搜索建图
// 记录扩展出的单词是在第几次扩展的时候得到的，key：单词，value：在广度优先搜索的第几层
Map<String, Integer> steps = new HashMap<String, Integer>();
steps.put(beginWord, 0);
// 记录了单词是从哪些单词扩展而来，key：单词，value：单词列表，这些单词可以变换到 key ，它们是一对多关系
Map<String, List<String>> from = new HashMap<String, List<String>>();
int step = 1;
boolean found = false;
int wordLen = beginWord.length();
Queue<String> queue = new ArrayDeque<String>();
queue.offer(beginWord);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String currWord = queue.poll();
char[] charArray = currWord.toCharArray();
// 将每一位替换成 26 个小写英文字母
for (int j = 0; j < wordLen; j++) {
char origin = charArray[j];
for (char c = 'a'; c <= 'z'; c++) {
charArray[j] = c;
String nextWord = String.valueOf(charArray);
if (steps.containsKey(nextWord) && step == steps.get(nextWord)) {
from.get(nextWord).add(currWord);
}
if (!dict.contains(nextWord)) {
continue;
}
// 如果从一个单词扩展出来的单词以前遍历过，距离一定更远，为了避免搜索到已经遍历到，且距离更远的单词，需要将它从 dict 中删除
dict.remove(nextWord);
// 这一层扩展出的单词进入队列
queue.offer(nextWord);
// 记录 nextWord 从 currWord 而来
from.putIfAbsent(nextWord, new ArrayList<>());
from.get(nextWord).add(currWord);
// 记录 nextWord 的 step
steps.put(nextWord, step);
if (nextWord.equals(endWord)) {
found = true;
}
}
charArray[j] = origin;
}
}
step++;
if (found) {
break;
}
}
// 第 2 步：回溯找到所有解，从 endWord 恢复到 beginWord ，所以每次尝试操作 path 列表的头部
if (found) {
Deque<String> path = new ArrayDeque<>();
path.add(endWord);
backtrack(from, path, beginWord, endWord, res);
}
return res;
}
public void backtrack(Map<String, List<String>> from, Deque<String> path, String beginWord, String cur, List<List<String>> res) {
if (cur.equals(beginWord)) {
res.add(new ArrayList<>(path));
return;
}
for (String precursor : from.get(cur)) {
path.addFirst(precursor);
backtrack(from, path, beginWord, precursor, res);
path.removeFirst();
}
}
}
cpp 解法, 执行用时: 68 ms, 内存消耗: 21.9 MB, 提交时间: 2023-09-23 10:57:28
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList) {
vector<vector<string>> res;
// 因为需要快速判断扩展出的单词是否在 wordList 里，因此需要将 wordList 存入哈希表，这里命名为「字典」
unordered_set<string> dict = {wordList.begin(), wordList.end()};
// 修改以后看一下，如果根本就不在 dict 里面，跳过
if (dict.find(endWord) == dict.end()) {
return res;
}
// 特殊用例处理
dict.erase(beginWord);
// 第 1 步：广度优先搜索建图
// 记录扩展出的单词是在第几次扩展的时候得到的，key：单词，value：在广度优先搜索的第几层
unordered_map<string, int> steps = {{beginWord, 0}};
// 记录了单词是从哪些单词扩展而来，key：单词，value：单词列表，这些单词可以变换到 key ，它们是一对多关系
unordered_map<string, set<string>> from = {{beginWord, {}}};
int step = 0;
bool found = false;
queue<string> q = queue<string>{{beginWord}};
int wordLen = beginWord.length();
while (!q.empty()) {
step++;
int size = q.size();
for (int i = 0; i < size; i++) {
const string currWord = move(q.front());
string nextWord = currWord;
q.pop();
// 将每一位替换成 26 个小写英文字母
for (int j = 0; j < wordLen; ++j) {
const char origin = nextWord[j];
for (char c = 'a'; c <= 'z'; ++c) {
nextWord[j] = c;
if (steps[nextWord] == step) {
from[nextWord].insert(currWord);
}
if (dict.find(nextWord) == dict.end()) {
continue;
}
// 如果从一个单词扩展出来的单词以前遍历过，距离一定更远，为了避免搜索到已经遍历到，且距离更远的单词，需要将它从 dict 中删除
dict.erase(nextWord);
// 这一层扩展出的单词进入队列
q.push(nextWord);
// 记录 nextWord 从 currWord 而来
from[nextWord].insert(currWord);
// 记录 nextWord 的 step
steps[nextWord] = step;
if (nextWord == endWord) {
found = true;
}
}
nextWord[j] = origin;
}
}
if (found) {
break;
}
}
// 第 2 步：回溯找到所有解，从 endWord 恢复到 beginWord ，所以每次尝试操作 path 列表的头部
if (found) {
vector<string> Path = {endWord};
backtrack(res, endWord, from, Path);
}
return res;
}
void backtrack(vector<vector<string>> &res, const string &Node, unordered_map<string, set<string>> &from,
vector<string> &path) {
if (from[Node].empty()) {
res.push_back({path.rbegin(), path.rend()});
return;
}
for (const string &Parent: from[Node]) {
path.push_back(Parent);
backtrack(res, Parent, from, path);
path.pop_back();
}
}
};