This content originally appeared on DEV Community 👩‍💻👨‍💻 and was authored by SalahElhossiny
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
This content originally appeared on DEV Community 👩‍💻👨‍💻 and was authored by SalahElhossiny
SalahElhossiny | Sciencx (2022-11-12T18:05:00+00:00) Word Ladder. Retrieved from https://www.scien.cx/2022/11/12/word-ladder/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.