Skip to content

126. Word Ladder II 👍

Approach 1: BFS + DFS (TLE)

  • Time: $O(|\texttt{wordList}| \cdot 26^{|\texttt{wordList[i]}|})$
  • Space: $O(\Sigma |\texttt{wordList[i]}| + \Sigma |\texttt{path[i]}|)$
 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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Solution {
 public:
  vector<vector<string>> findLadders(string beginWord, string endWord,
                                     vector<string>& wordList) {
    unordered_set<string> wordSet{wordList.begin(), wordList.end()};
    if (!wordSet.count(endWord))
      return {};

    // {"hit": ["hot"], "hot": ["dot", "lot"], ...}
    unordered_map<string, vector<string>> graph;

    // Build the graph from the beginWord to the endWord.
    if (!bfs(beginWord, endWord, wordSet, graph))
      return {};

    vector<vector<string>> ans;
    dfs(graph, beginWord, endWord, {beginWord}, ans);
    return ans;
  }

 private:
  bool bfs(const string& beginWord, const string& endWord,
           unordered_set<string>& wordSet,
           unordered_map<string, vector<string>>& graph) {
    unordered_set<string> currentLevelWords{beginWord};

    while (!currentLevelWords.empty()) {
      for (const string& word : currentLevelWords)
        wordSet.erase(word);
      unordered_set<string> nextLevelWords;
      bool reachEndWord = false;
      for (const string& parent : currentLevelWords) {
        vector<string> children;
        getChildren(parent, wordSet, children);
        for (const string& child : children) {
          if (wordSet.count(child)) {
            nextLevelWords.insert(child);
            graph[parent].push_back(child);
          }
          if (child == endWord)
            reachEndWord = true;
        }
      }
      if (reachEndWord)
        return true;
      currentLevelWords = move(nextLevelWords);
    }

    return false;
  }

  void getChildren(const string& parent, const unordered_set<string>& wordSet,
                   vector<string>& children) {
    string s(parent);

    for (int i = 0; i < s.length(); ++i) {
      const char cache = s[i];
      for (char c = 'a'; c <= 'z'; ++c) {
        if (c == cache)
          continue;
        s[i] = c;
        if (wordSet.count(s))
          children.push_back(s);
      }
      s[i] = cache;
    }
  }

  void dfs(const unordered_map<string, vector<string>>& graph,
           const string& word, const string& endWord, vector<string>&& path,
           vector<vector<string>>& ans) {
    if (word == endWord) {
      ans.push_back(path);
      return;
    }
    if (!graph.count(word))
      return;

    for (const string& child : graph.at(word)) {
      path.push_back(child);
      dfs(graph, child, endWord, move(path), ans);
      path.pop_back();
    }
  }
};

 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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Solution {
  public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord))
      return new ArrayList<>();

    // {"hit": ["hot"], "hot": ["dot", "lot"], ...}
    Map<String, List<String>> graph = new HashMap<>();

    // Build the graph from the beginWord to the endWord.
    if (!bfs(beginWord, endWord, wordSet, graph))
      return new ArrayList<>();

    List<List<String>> ans = new ArrayList<>();
    List<String> path = new ArrayList<>(Arrays.asList(beginWord));
    dfs(graph, beginWord, endWord, path, ans);
    return ans;
  }

  private boolean bfs(final String beginWord, final String endWord, Set<String> wordSet,
                      Map<String, List<String>> graph) {
    Set<String> currentLevelWords = new HashSet<>();
    currentLevelWords.add(beginWord);
    boolean reachEndWord = false;

    while (!currentLevelWords.isEmpty()) {
      for (final String word : currentLevelWords)
        wordSet.remove(word);
      Set<String> nextLevelWords = new HashSet<>();
      for (final String parent : currentLevelWords) {
        graph.putIfAbsent(parent, new ArrayList<>());
        for (final String child : getChildren(parent, wordSet)) {
          if (wordSet.contains(child)) {
            nextLevelWords.add(child);
            graph.get(parent).add(child);
          }
          if (child.equals(endWord))
            reachEndWord = true;
        }
      }
      if (reachEndWord)
        return true;
      currentLevelWords = nextLevelWords;
    }

    return false;
  }

  private List<String> getChildren(final String parent, Set<String> wordSet) {
    List<String> children = new ArrayList<>();
    StringBuilder sb = new StringBuilder(parent);

    for (int i = 0; i < sb.length(); ++i) {
      final char cache = sb.charAt(i);
      for (char c = 'a'; c <= 'z'; ++c) {
        if (c == cache)
          continue;
        sb.setCharAt(i, c);
        final String child = sb.toString();
        if (wordSet.contains(child))
          children.add(child);
      }
      sb.setCharAt(i, cache);
    }

    return children;
  }

  private void dfs(Map<String, List<String>> graph, final String word, final String endWord,
                   List<String> path, List<List<String>> ans) {
    if (word.equals(endWord)) {
      ans.add(new ArrayList<>(path));
      return;
    }
    if (!graph.containsKey(word))
      return;

    for (final String child : graph.get(word)) {
      path.add(child);
      dfs(graph, child, endWord, path, ans);
      path.remove(path.size() - 1);
    }
  }
}

 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
class Solution:
  def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
    wordSet = set(wordList)
    if endWord not in wordList:
      return []

    # {"hit": ["hot"], "hot": ["dot", "lot"], ...}
    graph: Dict[str, List[str]] = collections.defaultdict(list)

    # Build the graph from the beginWord to the endWord.
    if not self._bfs(beginWord, endWord, wordSet, graph):
      return []

    ans = []
    self._dfs(graph, beginWord, endWord, [beginWord], ans)
    return ans

  def _bfs(self, beginWord: str, endWord: str, wordSet: Set[str], graph: Dict[str, List[str]]) -> bool:
    currentLevelWords = {beginWord}

    while currentLevelWords:
      for word in currentLevelWords:
        wordSet.discard(word)
      nextLevelWords = set()
      reachEndWord = False
      for parent in currentLevelWords:
        for child in self._getChildren(parent, wordSet):
          if child in wordSet:
            nextLevelWords.add(child)
            graph[parent].append(child)
          if child == endWord:
            reachEndWord = True
      if reachEndWord:
        return True
      currentLevelWords = nextLevelWords

    return False

  def _getChildren(self, parent: str, wordSet: Set[str]) -> List[str]:
    children = []
    s = list(parent)

    for i, cache in enumerate(s):
      for c in string.ascii_lowercase:
        if c == cache:
          continue
        s[i] = c
        child = ''.join(s)
        if child in wordSet:
          children.append(child)
      s[i] = cache

    return children

  def _dfs(self, graph: Dict[str, List[str]], word: str, endWord: str, path: List[str], ans: List[List[str]]) -> None:
    if word == endWord:
      ans.append(path.copy())
      return

    for child in graph.get(word, []):
      path.append(child)
      self._dfs(graph, child, endWord, path, ans)
      path.pop()

Approach 2: Bidirectional BFS (TLE) + DFS

  • Time: $O(|\texttt{wordList}| \cdot 26^{|\texttt{wordList[i]}|})$
  • Space: $O(\Sigma |\texttt{wordList[i]}| + \Sigma |\texttt{path[i]}|)$
  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
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
class Solution {
 public:
  vector<vector<string>> findLadders(string beginWord, string endWord,
                                     vector<string>& wordList) {
    unordered_set<string> wordSet{wordList.begin(), wordList.end()};
    if (!wordSet.count(endWord))
      return {};

    // {"hit": ["hot"], "hot": ["dot", "lot"], ...}
    unordered_map<string, vector<string>> graph;

    // Build the graph from the beginWord to the endWord.
    if (!bfs(beginWord, endWord, wordSet, graph))
      return {};

    vector<vector<string>> ans;

    dfs(graph, beginWord, endWord, {beginWord}, ans);
    return ans;
  }

 private:
  bool bfs(const string& beginWord, const string& endWord,
           unordered_set<string>& wordSet,
           unordered_map<string, vector<string>>& graph) {
    unordered_set<string> forwardWords{beginWord};
    unordered_set<string> backwardWords{endWord};
    bool backward = false;

    while (!forwardWords.empty() && !backwardWords.empty()) {
      for (const string& word : forwardWords)
        wordSet.erase(word);
      for (const string& word : backwardWords)
        wordSet.erase(word);
      // Always expand the smaller queue.
      if (forwardWords.size() > backwardWords.size()) {
        swap(forwardWords, backwardWords);
        backward = !backward;
      }
      unordered_set<string> nextLevelWords;
      bool reachEndWord = false;
      for (const string& parent : forwardWords) {
        for (const string& child :
             getChildren(parent, wordSet, backwardWords)) {
          // Should check if the `child` is in the `backwardWords` since we
          // erase them at the beginning of each while loop.
          if (wordSet.count(child) || backwardWords.count(child)) {
            nextLevelWords.insert(child);
            if (backward)
              graph[child].push_back(parent);
            else
              graph[parent].push_back(child);
          }
          // We've reached the end word since there's a word in the
          // `forwardWords` connecting to a word in the `backwardWords`. Note
          // that we can't return here since we need to completely explore this
          // level.
          if (backwardWords.count(child))
            reachEndWord = true;
        }
      }
      if (reachEndWord)
        return true;
      forwardWords = move(nextLevelWords);
    }

    return true;
  }

  vector<string> getChildren(const string& parent,
                             const unordered_set<string>& wordSet,
                             const unordered_set<string>& backwardWords) {
    vector<string> children;
    string s(parent);

    for (int i = 0; i < s.length(); ++i) {
      const char cache = s[i];
      for (char c = 'a'; c <= 'z'; ++c) {
        if (c == cache)
          continue;
        s[i] = c;  // Now is `child`
        if (wordSet.count(s) || backwardWords.count(s))
          children.push_back(s);
      }
      s[i] = cache;
    }

    return children;
  }

  void dfs(const unordered_map<string, vector<string>>& graph,
           const string& word, const string& endWord, vector<string>&& path,
           vector<vector<string>>& ans) {
    if (word == endWord) {
      ans.push_back(path);
      return;
    }
    if (!graph.count(word))
      return;

    for (const string& child : graph.at(word)) {
      path.push_back(child);
      dfs(graph, child, endWord, move(path), ans);
      path.pop_back();
    }
  }
};

Approach 3: Pure BFS (TLE)

  • Time: $O(|\texttt{wordList}| \cdot 26^{|\texttt{wordList[i]}|})$
  • Space: $O(\Sigma |\texttt{wordList[i]}| + \Sigma |\texttt{path[i]}|)$
 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
class Solution {
 public:
  vector<vector<string>> findLadders(string beginWord, string endWord,
                                     vector<string>& wordList) {
    vector<vector<string>> ans;
    unordered_set<string> wordSet(wordList.begin(), wordList.end());
    queue<vector<string>> paths{{{beginWord}}};  // {{"hit"}}

    while (!paths.empty()) {
      unordered_set<string> currentLevelVisited;
      for (int sz = paths.size(); sz > 0; --sz) {
        vector<string> path = paths.front();
        paths.pop();                    // {"hit"}
        string lastWord = path.back();  // "hit"
        for (int i = 0; i < lastWord.length(); ++i) {
          char cache = lastWord[i];  // Cache = 'i'
          for (char c = 'a'; c <= 'z'; ++c) {
            lastWord[i] = c;                // "hit" -> "hot" (temporarily)
            if (wordSet.count(lastWord)) {  // Find "hot" in the wordSet.
              currentLevelVisited.insert(lastWord);  // Mark "hot" as visited.
              vector<string> nextPath(path);
              nextPath.push_back(lastWord);  // nextPath = {"hit", "hot"}
              if (lastWord == endWord)
                ans.push_back(nextPath);
              else
                paths.push(nextPath);
            }
          }
          lastWord[i] = cache;  // Convert "hot" back to "hit".
        }
      }
      for (const string& word : currentLevelVisited)
        wordSet.erase(word);
    }

    return ans;
  }
};

Approach 4: BFS + DFS w/ dist map for pruning childToParents map

  • Time: $O(|\texttt{wordList}|^2 + |\texttt{wordList}| \cdot 26^{|\texttt{wordList[i]}|})$
  • Space: $O(\Sigma |\texttt{wordList[i]}| + \Sigma |\texttt{path[i]}|)$
 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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class Solution {
 public:
  vector<vector<string>> findLadders(string beginWord, string endWord,
                                     vector<string>& wordList) {
    unordered_set<string> wordSet{wordList.begin(), wordList.end()};
    if (!wordSet.count(endWord))
      return {};

    // Build the adjacency list.
    // e.g. {"hit": ["hot"], "hot": ["dot", "lot"], ...}
    if (!wordSet.count(beginWord))
      wordList.push_back(beginWord);
    unordered_map<string, vector<string>> graph = getGraph(wordList);

    // childToParents[child] := the fastest parents to reach the `child`
    unordered_map<string, vector<string>> childToParents;
    if (!bfs(beginWord, endWord, graph, childToParents))
      return {};

    vector<vector<string>> ans;
    // Find the paths from the endWord to the beginWord.
    dfs(childToParents, endWord, beginWord, {endWord}, ans);
    return ans;
  }

 private:
  unordered_map<string, vector<string>> getGraph(
      const vector<string>& wordList) {
    unordered_map<string, vector<string>> graph;
    for (int i = 1; i < wordList.size(); ++i)
      for (int j = 0; j < i; ++j) {
        const string& u = wordList[i];
        const string& v = wordList[j];
        if (isConnect(u, v)) {
          graph[u].push_back(v);
          graph[v].push_back(u);
        }
      }
    return graph;
  }

  bool isConnect(const string& s, const string& t) {
    int count = 0;
    for (int i = 0; i < s.length(); ++i)
      if (s[i] != t[i])
        ++count;
    return count == 1;
  }

  bool bfs(const string& beginWord, const string& endWord,
           const unordered_map<string, vector<string>>& graph,
           unordered_map<string, vector<string>>& childToParents) {
    // dist[u] := the minimum distance to reach `u`
    unordered_map<string, int> dist{{beginWord, 0}};
    queue<string> q{{beginWord}};
    while (!q.empty()) {
      const string u = q.front();
      q.pop();
      if (u == endWord)
        return true;
      if (const auto it = graph.find(u); it != graph.cend())
        for (const string& v : it->second)
          if (!dist.count(v) || dist[u] + 1 < dist[v]) {
            dist[v] = dist[u] + 1;
            q.push(v);
            // Clear childToParents[v] since they take longer to reach v.
            childToParents[v] = {u};
          } else if (dist[u] + 1 == dist[v]) {
            // No need to q.push(v) since v is already in the queue.
            childToParents[v].push_back(u);
          }
    }
    return false;
  }

  void dfs(const unordered_map<string, vector<string>>& childToParents,
           const string& word, const string& beginWord, vector<string>&& path,
           vector<vector<string>>& ans) {
    if (word == beginWord) {
      ans.push_back({path.rbegin(), path.rend()});
      return;
    }
    if (const auto it = childToParents.find(word); it != childToParents.cend())
      for (const string& parent : it->second) {
        path.push_back(parent);
        dfs(childToParents, parent, beginWord, move(path), ans);
        path.pop_back();
      }
  }
};

Approach 5: BFS + DFS w/ distFromBeginWord map for pruning DFS

  • Time: $O(|\texttt{wordList}| \cdot 26^{|\texttt{wordList[i]}|})$
  • Space: $O(\Sigma |\texttt{wordList[i]}| + \Sigma |\texttt{path[i]}|)$
 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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Solution {
 public:
  vector<vector<string>> findLadders(string beginWord, string endWord,
                                     vector<string>& wordList) {
    unordered_set<string> wordSet{wordList.begin(), wordList.end()};
    if (!wordSet.count(endWord))
      return {};

    unordered_map<string, int> distFromBeginWord{{beginWord, 0}};
    if (!bfs(beginWord, endWord, wordSet, distFromBeginWord))
      return {};

    vector<vector<string>> ans;
    wordSet.insert(beginWord);
    dfs(endWord, beginWord, distFromBeginWord, wordSet, {endWord}, ans);
    return ans;
  }

 private:
  // Uses BFS to update the minimum steps to reach the `endWord` from the
  // `beginWord` by using the words in the `wordSet`.
  bool bfs(const string& beginWord, const string& endWord,
           unordered_set<string>& wordSet,
           unordered_map<string, int>& distFromBeginWord) {
    queue<string> q{{beginWord}};
    while (!q.empty()) {
      for (int sz = q.size(); sz > 0; --sz) {
        const string parent = q.front();
        q.pop();
        if (parent == endWord)
          return true;
        for (const string& child : getChildren(parent, wordSet)) {
          if (distFromBeginWord.count(child))
            continue;
          distFromBeginWord[child] = distFromBeginWord[parent] + 1;
          q.push(child);
        }
      }
    }
    return false;
  }

  void dfs(const string& word, const string& beginWord,
           const unordered_map<string, int>& distFromBeginWord,
           const unordered_set<string>& wordSet, vector<string>&& path,
           vector<vector<string>>& ans) {
    if (word == beginWord) {
      ans.push_back({path.rbegin(), path.rend()});
      return;
    }

    const int currDist = distFromBeginWord.at(word);

    for (const string& child : getChildren(word, wordSet)) {
      if (const auto it = distFromBeginWord.find(child);
          it != distFromBeginWord.cend() && it->second == currDist - 1) {
        path.push_back(child);
        dfs(child, beginWord, distFromBeginWord, wordSet, move(path), ans);
        path.pop_back();
      }
    }
  }

  vector<string> getChildren(const string& parent,
                             const unordered_set<string>& wordSet) {
    vector<string> children;
    string child(parent);
    for (int i = 0; i < child.length(); ++i) {
      const char cache = child[i];
      for (char c = 'a'; c <= 'z'; ++c) {
        if (c == cache)
          continue;
        child[i] = c;
        if (wordSet.count(child))
          children.push_back(child);
      }
      child[i] = cache;
    }
    return children;
  }
};