Word Ladder — LeetCode 127 Python Solution

The problem

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.

Example

Input

beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Output

5

Explanation

One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Python solution

while q1 and q2:
    if len(q1) <= len(q2):
        # Prioritize the queue with fewer elements for expansion
        extend(m1, m2, q1)
    else:
        extend(m2, m1, q2)


def extend(m1, m2, q):
    # New round of expansion
    for _ in range(len(q)):
        p = q.popleft()
        step = m1[p]
        for t in next(p):
            if t in m1:
                # Already visited before
                continue
            if t in m2:
                # The other direction has been searched, indicating that a shortest path has been found
                return step + 1 + m2[t]
            q.append(t)
            m1[t] = step + 1

Complexity

Pattern: Breadth-First Search

Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 127. Word Ladder is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.

The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.

Related problems