DEV Community

SalahElhossiny
SalahElhossiny

Posted on

1

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.


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

        s = set(wordList)
        l = list("abcdefghijklmnopqrstuvwxyz")

        queue = deque([])
        queue.append([beginWord,0])

        while queue:
            a, b = queue.popleft()
            if a == endWord:
                return b + 1
            for j in range(len(a)):
                for i in l:
                    if (a[:j] + i + a[j+1:]) in s \
                    and (a[:j] + i +a[j+1:]) != beginWord:
                        s.remove(a[:j]+i+a[j+1:])
                        queue.append([a[:j]+i+a[j+1:],b+1])

        return 0






Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay