127. word ladder

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.
• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

solution

The approach is pretty straightforward, by creating a graph that links words that are one character apart from each other, and then performing bfs to find the shortest path between beginWord and endWord.

The hard part is creating the graph in better than $O(n^2)$ time, because that times out. The key is to not directly link all the words together, but store each intermediate step as a key in the hashmap, where each word that can reach that intermediate step is added to the array at that key.

127-e1.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

hit

_it

h_t

hi_

intermediate steps

hit

hot

h_t

Link to original

Then, when we breadth-first search, we can just go through each possible intermediate step for the current node, and look at all the neighbors that also share this intermediate step.

def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
	g = defaultdict(list)
	
	for word in wordList:
		for i in range(len(word)):
			key = word[:i] + "_" + word[i+1:]
			g[key].append(word)
	
	q = deque([beginWord])
	visited = set()
	depth = 1
	
	while q:
		level_len = len(q)
		for i in range(level_len):
			cur_word = q.pop()
		
		if cur_word == endWord:
			return depth
		
		neighbors = []
		for i in range(len(cur_word)):
			key = cur_word[:i] + "_" + cur_word[i+1:]
			neighbors += g[key]
		
		for n in neighbors:
			if n not in visited:
				visited.add(n)
				q.appendleft(n)
				
		depth += 1
	
	return 0