search

dangoldin / blog.dangoldin.com-comments

Comments for blog.dangoldin.com
0 stars 0 forks source link

2016/07/17/coding-puzzle-word-transformation-through-valid-words/ #2

Open utterances-bot opened 3 years ago

utterances-bot commented 3 years ago

Coding puzzle: Word transformation through valid words - Dan Goldin

A neat coding puzzle I heard is to find the shortest path from one word to another where you're only allowed to change a single letter at every step and each step needs to be a valid word. I spent some time this morning writing the code to make it happen.

https://dangoldin.com/2016/07/17/coding-puzzle-word-transformation-through-valid-words/

marknathon449 commented 3 years ago

Really a great puzzle, different from many common ones with a interesting problem. Can I know why you used DFS instead of BFS? I think most people prefer DFS over BFS. But is using DFS due to "The recursive method of the Depth-First Search algorithm is implemented using stack." (source: DFS in Python) or because "DFS will take less memory than BFS" (source: DFS vs BFS)?

dangoldin commented 3 years ago

Not sure if you mistyped but I used BFS here. The idea being since we want the "shortest" path the BFS would end up finding it first. With a DFS you'd have to go through every path to find the shortest since it would want to explore each one in depth.