Problem

Given a source word, a target word, and an English dictionary, transform the source word to the target by changing, adding, or removing one character at a time, such that all intermediate words are valid English words. Return the transformation chain with the smallest number of intermediate words.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: 
source = "ad"
target = "bed"
dictionary = ["ad", "at", "ate", "bat", "bed", "bet", "cat", "ed", "table"]

Output: 
["ad", "ed", "bed"]

Explanation: 
"ad" -> "ed" (remove 'a'), "ed" -> "bed" (add 'b').

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: 
source = "cat"
target = "bet"
dictionary = ["ad", "at", "ate", "bat", "bed", "bet", "cat", "ed", "table"]

Output: 
["cat", "bat", "bet"]

Explanation: 
"cat" -> "bat" (change 'c' to 'b'), "bat" -> "bet" (change 'a' to 'e').

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: 
source = "at"
target = "ate"
dictionary = ["ad", "at", "ate", "bat", "bed", "bet", "cat", "ed", "table"]

Output: 
["at", "ate"]

Explanation: 
"at" -> "ate" (add 'e').

Similar Problem

Word Ladder - Get shortest ladder

Other Problems

Word Ladder 0 - Is a ladder there Word Ladder 1 - Get Ladder Length Word Ladder 2 - Get all the ladders

Solution

Method 1 - BFS

Reasoning / Intuition

The problem can be modeled as a graph where each node is a word, and there is an edge between two words if you can transform one into the other by changing, adding, or removing a single letter. The shortest transformation sequence can be found using Breadth-First Search (BFS).

Approach

  1. Build a graph where each word is a node, and edges exist between words that can be transformed into each other by one operation (change, add, remove a letter).
  2. Use BFS to find the shortest path from the source word to the target word.
  3. Return the path if found, otherwise return an empty list.

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include <vector>
#include <string>
#include <unordered_set>
#include <queue>
#include <unordered_map>

using namespace std;

class Solution {
public:
  vector<string> wordLadder(string source, string target, vector<string>& dictionary) {
    unordered_set<string> wordSet(dictionary.begin(), dictionary.end());
    if (!wordSet.count(source) || !wordSet.count(target)) return {};

    queue<vector<string>> q;
    q.push({source});
    unordered_set<string> visited;
    visited.insert(source);

    while (!q.empty()) {
      vector<string> path = q.front(); q.pop();
      string last = path.back();
      if (last == target) return path;
      for (const string& nei : neighbors(last, wordSet)) {
        if (!visited.count(nei)) {
          visited.insert(nei);
          vector<string> newPath = path;
          newPath.push_back(nei);
          q.push(newPath);
        }
      }
    }
    return {};
  }

private:
  vector<string> neighbors(const string& word, const unordered_set<string>& wordSet) {
    vector<string> res;
    string letters = "abcdefghijklmnopqrstuvwxyz";
    // Change a letter
    for (int i = 0; i < word.size(); ++i) {
      for (char c : letters) {
        if (c != word[i]) {
          string w = word;
          w[i] = c;
          if (wordSet.count(w)) res.push_back(w);
        }
      }
    }
    // Remove a letter
    for (int i = 0; i < word.size(); ++i) {
      string w = word.substr(0, i) + word.substr(i + 1);
      if (wordSet.count(w)) res.push_back(w);
    }
    // Add a letter
    for (int i = 0; i <= word.size(); ++i) {
      for (char c : letters) {
        string w = word.substr(0, i) + c + word.substr(i);
        if (wordSet.count(w)) res.push_back(w);
      }
    }
    return res;
  }
};
 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

import java.util.*;

class Solution {
  public List<String> wordLadder(String source, String target, List<String> dictionary) {
    Set<String> wordSet = new HashSet<>(dictionary);
    if (!wordSet.contains(source) || !wordSet.contains(target)) return Collections.emptyList();

    Queue<List<String>> queue = new LinkedList<>();
    queue.add(Arrays.asList(source));
    Set<String> visited = new HashSet<>();
    visited.add(source);

    while (!queue.isEmpty()) {
      List<String> path = queue.poll();
      String last = path.get(path.size() - 1);
      if (last.equals(target)) return path;
      for (String nei : neighbors(last, wordSet)) {
        if (!visited.contains(nei)) {
          visited.add(nei);
          List<String> newPath = new ArrayList<>(path);
          newPath.add(nei);
          queue.add(newPath);
        }
      }
    }
    return Collections.emptyList();
  }

  private Set<String> neighbors(String word, Set<String> wordSet) {
    Set<String> res = new HashSet<>();
    String letters = "abcdefghijklmnopqrstuvwxyz";
    // Change a letter
    for (int i = 0; i < word.length(); i++) {
      for (char c : letters.toCharArray()) {
        if (c != word.charAt(i)) {
          String w = word.substring(0, i) + c + word.substring(i + 1);
          if (wordSet.contains(w)) res.add(w);
        }
      }
    }
    // Remove a letter
    for (int i = 0; i < word.length(); i++) {
      String w = word.substring(0, i) + word.substring(i + 1);
      if (wordSet.contains(w)) res.add(w);
    }
    // Add a letter
    for (int i = 0; i <= word.length(); i++) {
      for (char c : letters.toCharArray()) {
        String w = word.substring(0, i) + c + word.substring(i);
        if (wordSet.contains(w)) res.add(w);
      }
    }
    return res;
  }
}
 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
37
38
39
40
41
42
43

from collections import deque

class Solution:
  def wordLadder(self, source, target, dictionary):
    word_set = set(dictionary)
    if target not in word_set or source not in word_set:
      return []

    def neighbors(word):
      res = set()
      letters = 'abcdefghijklmnopqrstuvwxyz'
      # Change a letter
      for i in range(len(word)):
        for c in letters:
          if c != word[i]:
            w = word[:i] + c + word[i+1:]
            if w in word_set:
              res.add(w)
      # Remove a letter
      for i in range(len(word)):
        w = word[:i] + word[i+1:]
        if w in word_set:
          res.add(w)
      # Add a letter
      for i in range(len(word)+1):
        for c in letters:
          w = word[:i] + c + word[i:]
          if w in word_set:
            res.add(w)
      return res

    queue = deque([[source]])
    visited = set([source])
    while queue:
      path = queue.popleft()
      last = path[-1]
      if last == target:
        return path
      for nei in neighbors(last):
        if nei not in visited:
          visited.add(nei)
          queue.append(path + [nei])
    return []

Complexity

  • ⏰ Time complexity: O(n * l^2 * 26), where n is the number of words in the dictionary and l is the maximum word length.
  • 🧺 Space complexity: O(n*l) for storing the graph and BFS queue.