Word Ladder
- 3 min read
- Graph
- LC-Hard
3 years ago
Solution
- Construct a graph of words where words one edge away from each other are words that differ by just one character
- You do this by taking wildstar words for each word, i.e. for hot, wildstar words are *ot, h*t, ho*.
- Base case: if end word is not in the given list, immediately return 0.
- Create an adjacency list. For every word in the given word list (also include the begin and end word):
- Key is the wildstar word, value is the list of words that match the wildstar word.
- For the first example, your adjacency list looks like the following:
defaultdict(<class 'list'>, {'*it': ['hit'], 'h*t': ['hit', 'hot'], 'hi*': ['hit'], '*og': ['cog', 'dog', 'log', 'cog'], 'c*g': ['cog', 'cog'], 'co*': ['cog', 'cog'], '*ot': ['hot', 'dot', 'lot'], 'ho*': ['hot'], 'd*t': ['dot'], 'do*': ['dot', 'dog'], 'd*g': ['dog'], 'l*t': ['lot'], 'lo*': ['lot', 'log'], 'l*g': ['log']})
-
The graphical representation of the above adjacency list is like the following:
-
Now, do a Breadth-first Search starting from the being word.
-
For each word in the queue, to get all neighbours, you need to get all the wildstar words for that word again, and then for each wildstar word, the words in the list are it's neighbours. You would add each of these neighbours to the queue for the next iteration.
- Technically, while doing the above step, you would be getting the same word we're currently at in our neighbours list, but since we're using a visited set, this would not be added back to the queue.
-
While doing the BFS, keep track of the number of BFSs done. When your target word is found, just return this number.
-
If you're out of the while loop, it means the end word wasn't found, so return 0.
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def getWildstarWords(self, word):
wildstar_words = []
for i in range(len(word)):
wildstar_word = word[:i] + '*' + word[i + 1:]
wildstar_words.append(wildstar_word)
return wildstar_words
def getWordNeighbours(self, adj, word):
neighbours = []
for wildstar_word in self.getWildstarWords(word):
for word in adj[wildstar_word]:
neighbours.append(word)
return neighbours
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
adj = defaultdict(list)
for word in [beginWord] + [endWord] + wordList:
for wildstar_word in self.getWildstarWords(word):
adj[wildstar_word].append(word)
q = deque([beginWord])
levels = 0
vis = set()
while q:
levels += 1
for _ in range(len(q)):
word = q.popleft()
if word == endWord:
return levels
vis.add(word)
for word_neighbour in self.getWordNeighbours(adj, word):
if word_neighbour not in vis:
q.append(word_neighbour)
return 0 # If code reached here then it means that the end word wasn't found, so return 0