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. 1.
Only one letter can be changed at a time.
2. 2.
Each transformed word must exist in the word list. Note that `beginWord`is not a transformed word.
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is `"hit" -> "hot" -> "dot" -> "dog" -> "cog"`, return its length `5`.
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.
The Idea: Build a graph. For this graph define a link between two words `a` and `b` if `difference(a,b) == 1`. Do this for every word. Then BFS through this graph, while using a `visited` map prohibits cyclic roots.
Complexity: `O(n^2 * m + n)` time where `m` is length of the word, and `n` is the number of words. `O(n^2 * m)` for prepossessing, and then `O(n)` time for BFS. Space complexity will be `O(n^2 + n + n)`; respectively for the graph itself, the visited set, and queue.
// assumption that size(a) == size(b)
int difference(const string &a, const string &b) {
int diff = 0;
for (int i = 0; i < a.size(); i++) {
if (a[i] != b[i]) diff++;
}
return diff;
}
unordered_map<string, unordered_set<string>> get_graph_diff_1(const vector<string> &wordList) {
unordered_map<string, unordered_set<string>> map;
map.reserve(wordList.size());
for (const string &s : wordList) {
map.insert({ s, unordered_set<string>() });
for (const string &s2 : wordList) {
if (difference(s2, s) == 1) {
map.at(s).insert(s2);
}
}
}
return map;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
wordList.push_back(beginWord);
unordered_map<string, unordered_set<string>> graph = get_graph_diff_1(wordList);
unordered_set<string> visited(wordList.begin(), wordList.end());
queue<pair<string, int>> q;
q.push({beginWord, 1});
while (!q.empty()) {
pair<string, int> front = q.front(); q.pop();
visited.erase(front.first);
for (auto &s : graph[front.first]) {
if (s == endWord)
return front.second + 1;
if (visited.find(s) != visited.end()) {
q.push({ s, front.second + 1 });
}
}
}
return 0;
}
Testing
int main() {
vector<string> word_bank = { "hot","dot","dog","lot","log","cog" };
cout << ladderLength("hit", "cog", word_bank) << endl;
vector<string> word_bank2 = { "hot", "dot", "dog", "lot", "log" };
cout << ladderLength("hit", "cog", word_bank2) << endl;
}
Python
import queue
class Solution:
def difference(self, a, b):
"""
:param a: str - word1
:param b: str - word2
:return: int - number of different characters between a and b
under the assumption that len(a) = len(b)
"""
diff = 0
for c1, c2 in zip(a,b):
if c1 != c2:
diff += 1
return diff
def get_graph_diff_1(self, word_list):
"""
:param word_list: List[str] - list of words
:return: 2d map - relationship of words that differ
by one connection
"""
return dict([word, set(word2 for word2 in word_list if self.difference(word, word2) == 1)] for word in word_list)
"""
:param endWord: str - target word to end
:param wordList: List[str] - bank of valid words (same length)
:return: int - minimum distance to get between start and end words
"""
wordList.append(beginWord)
graph = self.get_graph_diff_1(wordList)
visited = set(word for word in wordList)
q = queue.Queue()
q.put((beginWord, 1))
while not q.empty():
front = q.get()
if visited.__contains__(front):
visited.remove(front)
for word in graph[front]:
if word == endWord:
return front + 1
if visited.__contains__(word):
q.put((word, front + 1))
return 0
obj = Solution()
word_list = ["hot", "dot", "dog", "lot", "log"]