# 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.

Prepare the data

Because the starting word is not in the dictionary, I decided to add it. This will simplify building the graph.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- 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