Problem

Change a word into another by changing only only one character at a time. All intermediate words should be contained in a dictionary.

Examples

Example 1:

1
2
3
4
5

Input:
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output:
 true
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog"

Similar problems

Word Ladder 1 - Get Ladder Length Word Ladder 2 - Get all the ladders Word Ladder - Get shortest ladder Word Ladder - Get shortest ladder by changing, adding or removing one letter at a time

Solution

This problem is pretty simple if we can choose a proper data structure. Here is the second part of the problem - Word Ladder 1 - Get Ladder Length.

Method 1 - BFS

Example

Given a dictionary {"DOG", "COT", "COG", "FOG", "DOT"}, start word "FOG", and target word "COT".

From "FOG", we can generate new words by changing each letter to any other letter from ‘A’ to ‘Z’, but only keep those present in the dictionary. Here, "COG" and "DOG" are valid next steps.

If any transformed word matches the target, we’ve succeeded. Otherwise, we repeat the process for each valid transformation. If no sequence leads to the target, the search fails. For instance, "FOG" → "COG" → "COT" is a valid path.

This problem naturally fits a breadth-first search (BFS) approach, using a queue to explore all possible transformations level by level.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public boolean isNavigable(final String beginWord, final String endWord, final Set<String> dictionary) {  
    if (beginWord.length() != endWord.length()) {  
        return false;  
    }  
    if (beginWord.equals(endWord)) {  
        return true;  
    }  
  
    dictionary.remove(beginWord);  
  
    final Queue<String> queue = new LinkedList<String>();  
    queue.add(beginWord);  
  
    while (!queue.isEmpty()) {  
        final String top = queue.remove();  
  
        for (int i = 0; i<top.length(); i++) {  
            char[] temp = top.toCharArray();  
            for (char j = 'A'; j<'Z'; j++) {  
                temp[i] = j;  
  
                final String candidate = new String(temp);  
  
                if (candidate.equals(endWord)) {  
                    System.out.print("-->" + candidate);  
                    return true;                } else if (dictionary.contains(candidate)) {  
                    dictionary.remove(candidate);  
                    queue.add(candidate);  
                    System.out.print("-->" + candidate);  
                }  
            }  
        }  
    }  
  
    return false;  
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)