HIPTSI - WordLadder

Word Ladder is a problem that involves transforming one word in to another. The description on Leetcode is a little confusing so here is the description from dailycodingproblem.com

Given a start word, and end word, and a dictionary of valid words, find the shortest transformation sequence from start to end such that only one letter is changed at each step of the sequence, and each transformed word exists in the dictionary. If there is no possible transformation, return null. Each word in the dictionary have the same length as start and end and is lowercase.

so essentially -

and here is a link to the Leetcode problem - https://leetcode.com/problems/word-ladder/ 

Initial Thought Process

Here is how I Plan to Solve it (but not write any code)

• I have to traverse each character in the word
• At each position, create a new word by replacing the source character with the character at the same position in the target word
• Test if the new word exists in the library
• YES, save the new word and repeat this process with the new word
• NO, continue to the next character and repeat the process of replacing the character and checking the library
• If there are no more characters then this fails and there is no word ladder

We are essentially, attempting to create new word by sourcing the replacement words from the target word

Optimizations ?

Converting the words into arrays would help optimize the algorithm in some degree, as we could eliminate the characters that have already been replaced, thus cutting down on the number of matches we would need to perform. It would also make it easier to manipulate words.