An Interest In:
Web News this Week
- March 29, 2024
- March 28, 2024
- March 27, 2024
- March 26, 2024
- March 25, 2024
- March 24, 2024
- March 23, 2024
November 12, 2022 06:05 pm GMT
Original Link: https://dev.to/salahelhossiny/word-ladder-4o0d
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
Original Link: https://dev.to/salahelhossiny/word-ladder-4o0d
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To