word ladder

From http://www.programcreek.com/2012/12/leetcode-word-ladder/.

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that only one letter can be changed at a time, and each intermediate word must exist in the dictionary.

This one I didn't realize when I started working was in the tree section, and I didn't use any trees to solve it. This solution below is very brute force as a result. A better solution would be to construct a tree based on document distance of each word and use it to find the shortest path.

I'll try that solution out sometime later.

My solution below

  • Finds the valid starting words and ending words by seeing which words in the dictionary are within 1 letter different from each
  • Takes each of those and bruteforces each letter until a new word in the dictionary is found
  • Recurses untill an end word is found or no more possibilities exist
  • A list of all solutions is produced
  • The shortest one is returned

In Python:


	        

Leave a comment -

Elliot

https://www.emikek.com

I'm a .NET, PHP, Python, and Javascript developer. Also Project Manager, Scrum Master, and Juilliard trained violist. You cannot connect with me on Facebook, Twitter, or LinkedIn so don't ask.