题目描述

Given two words ( beginWord and endWord ), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord , such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.


Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.


代码

class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordSet(wordList.begin(), wordList.end());
if (!wordSet.count(endWord)) return 0;
unordered_map<string, int> pathCnt{{{beginWord, 1}}};
queue<string> q{{beginWord}};
while (!q.empty()) {
string word = q.front(); q.pop();
for (int i = 0; i < word.size(); ++i) {
string newWord = word;
for (char ch = 'a'; ch <= 'z'; ++ch) {
newWord[i] = ch;
if (wordSet.count(newWord) && newWord == endWord) return pathCnt[word] + 1;
if (wordSet.count(newWord) && !pathCnt.count(newWord)) {
q.push(newWord);
pathCnt[newWord] = pathCnt[word] + 1;
}
}
}
}
return 0;
}
};


class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordSet(wordList.begin(), wordList.end());
if (!wordSet.count(endWord)) return 0;
queue<string> q{{beginWord}};
int res = 0;
while (!q.empty()) {
for (int k = q.size(); k > 0; --k) {
string word = q.front(); q.pop();
if (word == endWord) return res + 1;
for (int i = 0; i < word.size(); ++i) {
string newWord = word;
for (char ch = 'a'; ch <= 'z'; ++ch) {
newWord[i] = ch;
if (wordSet.count(newWord) && newWord != word) {
q.push(newWord);
wordSet.erase(newWord);
}
}
}
}
++res;
}
return 0;
}
};


思路2

Dug => *ug
Dug => D*g
Dug => Du*


方法 1：广度优先搜索

算法
1. 对给定的 wordList 做预处理，找出所有的通用状态。将通用状态记录在字典中，键是通用状态，值是所有具有通用状态的单词。

2. 将包含 beginWord1 的元组放入队列中，1 代表节点的层次。我们需要返回 endWord 的层次也就是从 beginWord 出发的最短距离。

3. 为了防止出现环，使用访问数组记录。

4. 当队列中有元素的时候，取出第一个元素，记为 current_word

5. 找到 current_word 的所有通用状态，并检查这些通用状态是否存在其它单词的映射，这一步通过检查 all_combo_dict 来实现。

6. all_combo_dict 获得的所有单词，都和 current_word 共有一个通用状态，所以都和 current_word 相连，因此将他们加入到队列中。

7. 对于新获得的所有单词，向队列中加入元素 (word, level + 1) 其中 levelcurrent_word 的层次。

8. 最终当你到达期望的单词，对应的层次就是最短变换序列的长度。


class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {

// Since all words are of same length.
int L = beginWord.length();

// Dictionary to hold combination of words that can be formed,
// from any given word. By changing one letter at a time.
Map<String, List<String>> allComboDict = new HashMap<>();

wordList.forEach(
word -> {
for (int i = 0; i < L; i++) {
// Key is the generic word
// Value is a list of words which have the same intermediate generic word.
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
List<String> transformations = allComboDict.getOrDefault(newWord, new ArrayList<>());
allComboDict.put(newWord, transformations);
}
});

// Queue for BFS
Queue<Pair<String, Integer>> Q = new LinkedList<>();

// Visited to make sure we don't repeat processing same word.
Map<String, Boolean> visited = new HashMap<>();
visited.put(beginWord, true);

while (!Q.isEmpty()) {
Pair<String, Integer> node = Q.remove();
String word = node.getKey();
int level = node.getValue();
for (int i = 0; i < L; i++) {

// Intermediate words for current word
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);

// Next states are all the words which share the same intermediate state.
for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<>())) {
// If at any point if we find what we are looking for
// i.e. the end word - we can return with the answer.
return level + 1;
}
// Otherwise, add it to the BFS Queue. Also mark it visited
}
}
}
}

return 0;
}
}

复杂度分析
• 时间复杂度：O(M \times N)O(M×N)，其中 MM 是单词的长度 NN 是单词表中单词的总数。找到所有的变换需要对每个单词做 MM 次操作。同时，最坏情况下广度优先搜索也要访问所有的 NN 个单词。
• 空间复杂度：O(M \times N)O(M×N)，要在 all_combo_dict 字典中记录每个单词的 MM 个通用状态。访问数组的大小是 NN。广搜队列最坏情况下需要存储 NN 个单词。

方法 2：双向广度优先搜索

算法
1. 算法与之前描述的标准广搜方法相类似。

2. 唯一的不同是我们从两个节点同时开始搜索，同时搜索的结束条件也有所变化。

3. 我们现在有两个访问数组，分别记录从对应的起点是否已经访问了该节点。

4. 如果我们发现一个节点被两个搜索同时访问，就结束搜索过程。因为我们找到了双向搜索的交点。过程如同从中间相遇而不是沿着搜索路径一直走。

1. 最短变换序列的长度就是中间节点在两边的层次之和。因此，我们可以在访问数组中记录节点的层次。


class Solution {

private int L;
private Map<String, List<String>> allComboDict;

Solution() {
this.L = 0;

// Dictionary to hold combination of words that can be formed,
// from any given word. By changing one letter at a time.
this.allComboDict = new HashMap<>();
}

private int visitWordNode(
Queue<Pair<String, Integer>> Q,
Map<String, Integer> visited,
Map<String, Integer> othersVisited) {

Pair<String, Integer> node = Q.remove();
String word = node.getKey();
int level = node.getValue();

for (int i = 0; i < this.L; i++) {

// Intermediate words for current word
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);

// Next states are all the words which share the same intermediate state.
for (String adjacentWord : this.allComboDict.getOrDefault(newWord, new ArrayList<>())) {
// If at any point if we find what we are looking for
// i.e. the end word - we can return with the answer.
}

// Save the level as the value of the dictionary, to save number of hops.
}
}
}
return -1;
}

public int ladderLength(String beginWord, String endWord, List<String> wordList) {

if (!wordList.contains(endWord)) {
return 0;
}

// Since all words are of same length.
this.L = beginWord.length();

wordList.forEach(
word -> {
for (int i = 0; i < L; i++) {
// Key is the generic word
// Value is a list of words which have the same intermediate generic word.
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
List<String> transformations =
this.allComboDict.getOrDefault(newWord, new ArrayList<>());
this.allComboDict.put(newWord, transformations);
}
});

// Queues for birdirectional BFS
// BFS starting from beginWord
Queue<Pair<String, Integer>> Q_begin = new LinkedList<>();
// BFS starting from endWord
Queue<Pair<String, Integer>> Q_end = new LinkedList<>();

// Visited to make sure we don't repeat processing same word.
Map<String, Integer> visitedBegin = new HashMap<>();
Map<String, Integer> visitedEnd = new HashMap<>();
visitedBegin.put(beginWord, 1);
visitedEnd.put(endWord, 1);

while (!Q_begin.isEmpty() && !Q_end.isEmpty()) {

// One hop from begin word
int ans = visitWordNode(Q_begin, visitedBegin, visitedEnd);
if (ans > -1) {
return ans;
}

// One hop from end word
ans = visitWordNode(Q_end, visitedEnd, visitedBegin);
if (ans > -1) {
return ans;
}
}

return 0;
}
}

复杂度分析
• 时间复杂度： O(M \times N)O(M×N)，其中 MM 是单词的长度 NN 是单词表中单词的总数。与单向搜索相同的是，找到所有的变换需要 M * NM∗N 次操作。但是搜索时间会被缩小一半，因为两个搜索会在中间某处相遇。
• 空间复杂度： O(M \times N)O(M×N)，要在 all_combo_dict 字典中记录每个单词的 MM 个通用状态，这与单向搜索相同。但是因为会在中间相遇，所以双向搜索的搜索空间变小。

评论
0 评论