Leetcode – Word Ladder solution In Java

Tags: , ,

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. For example, given:

One shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, the program should return its length 5.

Analysis

From each word, we can change its letter one by one, thus a bread first search tree is constructed. The problem becomes to find the shortest path from the start word to the end word. A bread first search (BFS) algorithm can be used as it guarantees the path is the shortest. See the following tree:

leetcode word   ladder

To implement the BFS, we use a queue. Initially only the start word is in it. Then all the words generated from start word are put into the queue. We continue the process of each of the generated words in the search process.  To prevent duplication, we need a hashTable to record the visited word.

The following is the implementation using Java.

The above implementation can not pass large test cases. The reason is that the visited Hashtable consumes too much memory. We can remove the words in the word dictionary instead. See the following code which can pass all the test cases: