Word ladders using a "list of lists" approach, a list of paths
Breadth first version

EXAMPLE, BREADTH FIRST (queue - add to the end of the list, remove from the front of the list) These operations are often called enqueue and dequeue.

1. Initial list of paths is [["cat"]] - one path with one word.

2. Expand the item in this path (the front of the queue). "cat" -->"bat", "cab","cam","can","cap", "car", "caw", "cot", ...etc.

   NOTE THAT THE POSSIBLE PATH LISTS ARE EACH CONSTRUCTED IN REVERSE ORDER IN THESE EXAMPLES..."cat" --> "bat" is represented as ["bat", "cat"]

3. Create a list of length two paths from "cat" to each of the words in this extended list.

   [["bat", "cat"], ["cab", "cat"], ["cam", "cat"], ["can", "cat"], ["cap", "cat"], ["car", "cat"], ["caw", "cat"], ["cot", "cat"], ["cut", "cat"], ["eat", "cat"], ["fat", "cat"], ["hat", "cat"], ["mat", "cat"], ["oat", "cat"], ["pat", "cat"], ["rat", "cat"], ["sat", "cat"], ["vat", "cat"]]

4. Remove the possible path that is on the front of this queue of paths - ["bat", "cat"] Check if the next word, the word extended from "cat", is the goal (target). "bat" is not "cab", the target.

5. The goal has not been reached, so continue with this process. Expand the possible words from "bat", the unsuccessful word.

   "bat"--> "bad", "bag", "bah", "ban", "bar", "bay", "bet", "bit", "but", "eat", etc

6. Make a list of all of the new three word paths ["cat" --> "bat" --> each of these new words]:

   [["bad", "bat", "cat"], ["bag", "bat", "cat"], ["bah", "bat", "cat"], ["ban", "bat", "cat"], ["bar", "bat", "cat"], ["bay", "bat", "cat"], ["bet", "bat", "cat"], ["bit", "bat", "cat"], ["but", "bat", "cat"], ["eat", "bat", "cat"], ["fat", "bat", "cat"], ["hat", "bat", "cat"], ["mat", "bat", "cat"], ["oat", "bat", "cat"], ["pat", "bat", "cat"], ["rat", "bat", "cat"], ["sat", "bat", "cat"], ["vat", "bat", "cat"]]

7. We're using a queue data structure for breadth first. Add this new list of possible three word paths to the end of the queue in #3 above:

   [["cab", "cat"], ["cam", "cat"], ["can", "cat"], ["cap", "cat"], ["car", "cat"], ["caw", "cat"], ["cot", "cat"], ["cut", "cat"], ["eat", "cat"], ["fat", "cat"], ["hat", "cat"], ["mat", "cat"], ["oat", "cat"], ["pat", "cat"], ["rat", "cat"], ["sat", "cat"], ["vat", "cat"], ["bad", "bat", "cat"], ["bag", "bat", "cat"], ["bah", "bat", "cat"], ["ban", "bat", "cat"], ["bar", "bat", "cat"], ["bay", "bat", "cat"], ["bet", "bat", "cat"], ["bit", "bat", "cat"], ["but", "bat", "cat"], ["eat", "bat", "cat"], ["fat", "bat", "cat"], ["hat", "bat", "cat"], ["mat", "bat", "cat"], ["oat", "bat", "cat"], ["pat", "bat", "cat"], ["rat", "bat", "cat"], ["sat", "bat", "cat"], ["vat", "bat", "cat"]]

8. Remove the next candidate from the front of this queue - ["cab", "cat"]. "cab" is the target word, so the list of the path ["cab", "cat"] is returned as the solution.

9. Note that if the goal/target had not been reached, continuing with this process would mean that all of these two word paths would be checked before any of the three word paths. If the three word paths were checked (all the two word paths had been removed), new four word paths would begin to be added at the end of the queue, after all of the three word paths.

Word ladders using a "list of lists" approach, a list of paths -
Depth first version

EXAMPLE, DEPTH FIRST: stack - add to the top (front) of the stack, remove from the top of the stack. These operations are often called push and pop.

Find a path from "cat" to "bad".

1. Initial list of paths is [["cat"]] - one path with one word.

2. Expand the item in this path (the front of the queue). "cat" -->"bat", "cab","cam","can","cap", "car", "caw", "cot", ...etc.

3. Create a list of length two paths from "cat" to each of the words in this extended list.

   [["bat", "cat"], ["cab", "cat"], ["cam", "cat"], ["can", "cat"], ["cap", "cat"], ["car", "cat"], ["caw", "cat"], ["cot", "cat"], ["cut", "cat"], ["eat", "cat"], ["fat", "cat"], ["hat", "cat"], ["mat", "cat"], ["oat", "cat"], ["pat", "cat"], ["rat", "cat"], ["sat", "cat"], ["vat", "cat"]]

4. Remove the possible path that is on the front of this queue of paths - ["bat", "cat"] Check if the next word, the word extended from "cat", is the goal (target). "bat" is not "cab", the target.

5. The goal has not been reached, so continue with this process. Expand the possible words from "bat", the unsuccessful word.

   "bat"--> "bad", "bag", "bah", "ban", "bar", "bay", "bet", "bit", "but", "eat", etc

6. Make a list of all of the new three word paths ["cat" --> "bat" --> each of these new words]: [["bad", "bat", "cat"], ["bag", "bat", "cat"], ["bah", "bat", "cat"], ["ban", "bat", "cat"], ["bar", "bat", "cat"], ["bay", "bat", "cat"], ["bet", "bat", "cat"], ["bit", "bat", "cat"], ["but", "bat", "cat"], ["eat", "bat", "cat"], ["fat", "bat", "cat"], ["hat", "bat", "cat"], ["mat", "bat", "cat"], ["oat", "bat", "cat"], ["pat", "bat", "cat"], ["rat", "bat", "cat"],

7. We're using a stack data structure for depth first. Add this new list of possible three word paths to the top (front) of the stack in #3 above:

   [["bad", "bat", "cat"], ["bag", "bat", "cat"], ["bah", "bat", "cat"], ["ban", "bat", "cat"], ["bar", "bat", "cat"], ["bay", "bat", "cat"], ["bet", "bat", "cat"], ["bit", "bat", "cat"], ["but", "bat", "cat"], ["eat", "bat", "cat"], ["fat", "bat", "cat"], ["hat", "bat", "cat"], ["mat", "bat", "cat"], ["oat", "bat", "cat"], ["pat", "bat", "cat"], ["rat", "bat", "cat"], ["sat", "bat", "cat"], ["vat", "bat", "cat"], ["cab", "cat"], ["cam", "cat"], ["can", "cat"], ["cap", "cat"], ["car", "cat"], ["caw", "cat"], ["cot", "cat"], ["cut", "cat"], ["eat", "cat"], ["fat", "cat"], ["hat", "cat"], ["mat", "cat"], ["oat", "cat"], ["pat", "cat"], ["rat", "cat"], ["sat", "cat"], ["vat", "cat"]]

8. Remove (pop) the next candidate from the top (front) of this stack - ["bad", "bat", "cat"]. "bad" is the target word, so the list of the path ["bad", "bat", "cat"] is returned as the solution.

9. Note that if the goal/target had not been reached, continuing with this process would mean that the next paths to be checked would be four word paths extending from ["bad", "bat", "cat"]. If the solution were not found, then five word paths would be added to the front (top) of the current stack. These five word paths would be determined from the particular four word path that happened to be at the top of the stack. With this stack approach, depth first search may not find a solution and may involved paths that are too long. A depth limited approach handles this problem. Once paths of a certain length are reached, paths of shorter lengths are returned to by backtracking from the most recent recursive call.