126. Word Ladder II LeetCode Solution

In this guide, you will get 126. Word Ladder II LeetCode Solution with the best time and space complexity. The solution to Word Ladder II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Word Ladder II solution in C++
4. Word Ladder II solution in Java
5. Word Ladder II solution in Python
6. Additional Resources

Problem Statement of Word Ladder II

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:

Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, …, sk].

Example 1:

Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
Output: [[“hit”,”hot”,”dot”,”dog”,”cog”],[“hit”,”hot”,”lot”,”log”,”cog”]]
Explanation: There are 2 shortest transformation sequences:
“hit” -> “hot” -> “dot” -> “dog” -> “cog”
“hit” -> “hot” -> “lot” -> “log” -> “cog”

Example 2:

Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
Output: []
Explanation: The endWord “cog” is not in wordList, therefore there is no valid transformation sequence.

Constraints:

1 <= beginWord.length <= 5
endWord.length == beginWord.length
1 <= wordList.length <= 500
wordList[i].length == beginWord.length
beginWord, endWord, and wordList[i] consist of lowercase English letters.
beginWord != endWord
All the words in wordList are unique.
The sum of all shortest transformation sequences does not exceed 105.

Complexity Analysis

• Time Complexity: O(|\texttt{wordList}| \cdot 26^{|\texttt{wordlist[i]}|})
• Space Complexity: O(\Sigma |\texttt{wordlist[i]}| + \Sigma |\texttt{path[i]}|)

126. Word Ladder II LeetCode Solution in C++

class Solution {
 public:
  vector<vector<string>> findLadders(string beginWord, string endWord,
                                     vector<string>& wordList) {
    unordered_set<string> wordSet{wordList.begin(), wordList.end()};
    if (!wordSet.contains(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.contains(child)) {
            nextLevelWords.insert(child);
            graph[parent].push_back(child);
          }
          if (child == endWord)
            reachEndWord = true;
        }
      }
      if (reachEndWord)
        return true;
      currentLevelWords = std::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.contains(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.contains(word))
      return;

    for (const string& child : graph.at(word)) {
      path.push_back(child);
      dfs(graph, child, endWord, std::move(path), ans);
      path.pop_back();
    }
  }
};
/* code provided by PROGIEZ */

126. Word Ladder II LeetCode Solution in Java

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<>(List.of(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);
    }
  }
}
// code provided by PROGIEZ

126. Word Ladder II LeetCode Solution in Python

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()
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.