The Pseudo-Code

The pseudo-code here is a representation of the search procedure.

Time Complexity

To find whether or not two words are adjacent, n comparisons are required, where n is the length of each word. In the worst-case scenario, all pairs of words would be compared by making (O(m^2)) comparisons. If there are m words, the time complexity is (O(m^2n)). We are using the queue data structure, which in the worst-case scenario would have m entries, making the space complexity O(mn).

Concluding Remarks

We have described a simple algorithm based on breadth first search to solve the word ladder. The algorithm can be made more efficient by pre-processing and using a more complex data structure to store an intermediate representation of words that would make searching through the dictionary more efficient and faster. However, this would be at the cost of increasing the space complexity.

xxxxxxxxxx

Method: solve

Input: startW, endW, dictionary

​

Data structure: Queue Q of nodes.

               Node data is called strNode that keeps track of the word and level

​

1. level = 1

2. Add to the end of queue (startW,level). 

3. Remove from dictionary (startW)

4. Repeat till endW found or dictionary is empty

    i.   Remove word w and level from front of queue

    ii.  Search dictionary for all words adjacent to w 

    iii. If an adjacent word is endW then stop

    iv.  level = level+1

    iv.  Add to the end of queue all adjancent (word,level) pairs

    v.   Remove all adjacent words from dictionary

5. Return level