127 Word Ladder
Given two words (
beginWordand 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
beginWordis 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
_beginWordand_endWordare 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)
def ladderLength(self, beginWord, endWord, wordList):
"""
:param beginWord: str - word to start with
: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[0]):
visited.remove(front[0])
for word in graph[front[0]]:
if word == endWord:
return front[1] + 1
if visited.__contains__(word):
q.put((word, front[1] + 1))
return 0
obj = Solution()
word_list = ["hot", "dot", "dog", "lot", "log"]
print(obj.ladderLength("hit", "cog", word_list))
Last modified 4yr ago