Leetcode: Word Ladder II

I want to share my solution to a coding challenge I found on Leetcode. While the problem doesn't appear to be too hard, it took me a few hours to come up with a decent solution.

Because I wanted to focus on the solution, I decided to leverage the existing package with includes Graph data structure implementation (pythonds).

To use pythonds package in your code, first pip install the package then reference the library in your code:
from pythonds.graphs import Graph from pythonds.basic import Queue

I broke the problem into 3 parts:
1. Preparing the data.
2. Building a graph to prepresent the relationship between individual words.
3. Writing the a graph traversal algorithm to find all the paths from word A to word B.

1. Prepare the data
   Because the starting word is not in the dictionary, I decided to add it. This will simplify building the graph.

2. Build the graph
   # build the graph def build_graph(words): d = {} g = Graph() for word in words: for i in range(len(word)): bucket = word[:i] + '_' + word[i+1:] if bucket in d: d[bucket].append(word) else: d[bucket] = [word]
for bucket in d.keys(): for wordA in d[bucket]: for wordB in d[bucket]: if wordA != wordB: g.addEdge(wordA,wordB) return g

3. Traverse the graph
   def find_path(g,start, end, path): start.setColor('black') path.append(start) if start.getId() == end.getId(): #print path for p in path: print p.getId(), print "" else: for nbr in start.getConnections(): if nbr.getColor() == 'white': find_path(g, nbr, end, path) path.pop() start.setColor("white")

Now let's test the code
path=[] g = build_graph(words)
find_path(g, g.getVertex("hit"), g.getVertex("cog"), path)


And here is the output:
hit hot lot log dog cog hit hot lot log cog
hit hot lot dot dog log cog
hit hot lot dot dog cog
hit hot dot dog log cog
hit hot dot dog cog
hit hot dot lot log dog cog
hit hot dot lot log cog