Skip to content

Instantly share code, notes, and snippets.

@merriam merriam/x.py
Created Nov 13, 2018

Embed
What would you like to do?
import collections
class Solution:
def findLadders(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: List[List[str]]
"""
wordListSet = set(wordList + [beginWord])
graph = collections.defaultdict(list)
q = set([beginWord])
count = 0
result = []
while q:
count += 1
newQ = set()
for word in q:
wordListSet.remove(word)
for word in q:
if word == endWord:
self.getAllPaths(graph, beginWord, endWord, result, [])
else:
for i in range(len(word)):
for sub in 'abcdefghijklmnopqrstuvwxyz':
if sub != word[i]:
newWord = word[:i] + sub + word[i + 1:]
if newWord in wordListSet:
graph[word].append(newWord)
newQ.add(newWord)
q = newQ
return result
def getAllPaths(self, graph, node, target, result, output):
# This is just a backtracking pre-order traversal DFS on a DAG.
output.append(node)
if node == target:
result.append(output[:])
else:
for child in graph[node]:
self.getAllPaths(graph, child, target, result, output)
output.pop()
beginWord = 'aaa'
endWord = 'cdd'
wordList = ['aab', 'aba', 'abb', 'cbb', 'cbd', 'cdb', 'cdd']
s = Solution()
out = s.findLadders(beginWord, endWord, wordList)
print(out)
# [['aaa', 'aba', 'abb', 'cbb', 'cdb', 'cdd'], ['aaa', 'aba', 'abb', 'cbb', 'cbd', 'cdd'],
# ['aaa', 'aab', 'abb', 'cbb', 'cdb', 'cdd'], ['aaa', 'aab', 'abb', 'cbb', 'cbd', 'cdd']]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.