博文中会简要介绍Leetcode P0127题目分析及解题思路。
“Word Ladder”这道题是一道比较经典的广度优先搜索题目，利用初始的word数组构造一个无向图，每个结点代表一个单词，然后从起始单词所代表的结点开始BFS即可。
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:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list.
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.
最基本的思路是通过word数组来构建一个无向图，然后从起始单词所指向的结点使用广度优先搜索，这样一来一旦搜索到和结束单词一样的单词，此时的路径长度一定是最短的。
以下是Java的题解代码实现。
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int N = wordList.size();
List<List<Integer>> adjList = new ArrayList<>();
for (int itr=0; itr<=N; ++itr)
adjList.add(new ArrayList<>());
// Build graph
for (int idx=0; idx<N; ++idx) {
if (this.compare(beginWord, wordList.get(idx)))
adjList.get(0).add(idx+1);
}
for (int i1=0; i1<N; ++i1) {
for (int j2=i1+1; j2<N; ++j2) {
if (this.compare(wordList.get(i1), wordList.get(j2))) {
adjList.get(i1+1).add(j2+1);
adjList.get(j2+1).add(i1+1);
}
}
}
// BFS
boolean[] isVisited = new boolean[N+1];
Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
queue.offer(new Pair<>(0, 1));
while (!queue.isEmpty()) {
Pair<Integer, Integer> vertex = queue.poll();
int u = vertex.getKey(), steps = vertex.getValue();
isVisited[u] = true;
for (int v: adjList.get(u)) {
if (!isVisited[v]) {
if (endWord.equals(wordList.get(v-1)))
return steps+1;
queue.offer(new Pair<>(v, steps+1));
}
}
}
return 0;
}
private boolean compare(String s, String p) {
int diff = 0;
for (int itr=0; itr<s.length(); ++itr) {
if (s.charAt(itr) != p.charAt(itr))
++diff;
}
return (diff == 1);
}
}
以下的Java的题解代码是对BFS思路的优化，通过反向映射，即将单词改变一个字母后可能产生的形态（即Wildcards）映射到可以具有这样形态的实际单词上，来优化BFS对邻接结点的遍历。
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 all generic wildcards that can be formed, from any given word.
// By changing one letter at a time.
HashMap<String, ArrayList<String>> wildcard2WordMap = new HashMap<String, ArrayList<String>>();
wordList.forEach(
word -> {
for (int i = 0; i < L; i++) {
// Key is the generic widlcard
// Value is a list of words which have the same intermediate generic word.
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
ArrayList<String> transformations =
wildcard2WordMap.getOrDefault(newWord, new ArrayList<String>());
transformations.add(word);
wildcard2WordMap.put(newWord, transformations);
}
});
// Queue for BFS
Queue<Pair<String, Integer>> Q = new LinkedList<Pair<String, Integer>>();
Q.add(new Pair(beginWord, 1));
// Visited to make sure we don't repeat processing same word.
HashMap<String, Boolean> visited = new HashMap<String, Boolean>();
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 : wildcard2WordMap.getOrDefault(newWord, new ArrayList<String>())) {
// If at any point if we find what we are looking for
// i.e. the end word - we can return with the answer.
if (adjacentWord.equals(endWord)) {
return level + 1;
}
// Otherwise, add it to the BFS Queue. Also mark it visited
if (!visited.containsKey(adjacentWord)) {
visited.put(adjacentWord, true);
Q.add(new Pair(adjacentWord, level + 1));
}
}
}
}
return 0;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
wordList.push_back(beginWord);
// O(1) look-up time
unordered_map<string, vector<string>> generic2words;
unordered_map<string, vector<string>> word2generics;
// Construct map
for_each(wordList.cbegin(), wordList.cend(), [&word2generics, &generic2words](string word) {
// Generate generic wildcards
string wildcard(word);
for (int j2=0; j2<word.length(); ++j2) {
wildcard[j2] = '*';
// Update generics
word2generics[word].push_back(wildcard);
// Update words
generic2words[wildcard].push_back(word);
// Restore generic wildcard
wildcard[j2] = word[j2];
}
});
// BFS
unordered_map<string, bool> visited;
queue<pair<string, int>> nodes_queue;
int len = 1;
pair<string, int> root(beginWord, len);
nodes_queue.push(root);
visited[beginWord] = false;
while (!nodes_queue.empty()) {
pair<string, int> curr = nodes_queue.front();
nodes_queue.pop();
// If visited
if (visited[curr.first])
continue;
visited[curr.first] = true;
for (string generic: word2generics[curr.first]) {
for (string word: generic2words[generic]) {
if (word == endWord) {
return curr.second+1;
}
if (!visited[word]) {
nodes_queue.push(pair<string, int> {word, curr.second+1});
}
}
}
}
return 0;
}
};