Word Ladder II LeetCode Solution

Last updated on October 5th, 2024 at 09:25 pm

Here, We see Word Ladder II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Array, Backtracking, Breadth-First Search, String

Companies

Amazon, Yelp

Level of Question

Hard

Word Ladder II LeetCode Solution

Word Ladder II LeetCode Solution

Problem Statement

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.

1. Word Ladder II LeetCode Solution C++

class Solution {
public:
bool able(string s,string t){
    int c=0;
    for(int i=0;i&lt;s.length();i++)
        c+=(s[i]!=t[i]);
    return c==1;
}
void bfs(vector&lt;vector&lt;int&gt;&gt; &amp;g,vector&lt;int&gt; parent[],int n,int start,int end){
    vector &lt;int&gt; dist(n,1005);
    queue &lt;int&gt; q;
    q.push(start);
    parent[start]={-1};
    dist[start]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int u:g[x]){
            if(dist[u]&gt;dist[x]+1){
                dist[u]=dist[x]+1;
                q.push(u);
                parent[u].clear();
                parent[u].push_back(x);
            }
            else if(dist[u]==dist[x]+1)
                parent[u].push_back(x);
        }
    }
}
void shortestPaths(vector&lt;vector&lt;int&gt;&gt; &amp;Paths, vector&lt;int&gt; &amp;path, vector&lt;int&gt; parent[],int node){
    if(node==-1){
        Paths.push_back(path);
        return ;
    }
    for(auto u:parent[node]){
        path.push_back(u);
        shortestPaths(Paths,path,parent,u);
        path.pop_back();
    }
}
vector&lt;vector&lt;string&gt;&gt; findLadders(string beginWord, string endWord, vector&lt;string&gt;&amp; wordList) {
    int n=wordList.size(),start=-1,end=-1;
    vector&lt;vector&lt;string&gt;&gt; ANS;
    for(int i=0;i&lt;n;i++){
        if(wordList[i]==beginWord)
            start=i;
        if(wordList[i]==endWord)
            end=i;
    }
    if(end==-1)
        return ANS;
    if(start==-1){
        wordList.emplace(wordList.begin(),beginWord);
        start=0;
        end++;
        n++;
    }
    vector&lt;vector&lt;int&gt;&gt; g(n,vector&lt;int&gt;()),Paths;
    vector&lt;int&gt; parent[n],path;
    for(int i=0;i&lt;n-1;i++)
        for(int j=i+1;j&lt;n;j++)
            if(able(wordList[i],wordList[j])){
                g[i].push_back(j);
                g[j].push_back(i);
            }
    bfs(g,parent,n,start,end); 
    shortestPaths(Paths,path,parent,end);
    for(auto u:Paths){
        vector &lt;string&gt; now;
        for(int i=0;i&lt;u.size()-1;i++)
            now.push_back(wordList[u[i]]);
        reverse(now.begin(),now.end());
        now.push_back(wordList[end]);
        ANS.push_back(now);
    }
    return ANS;
}
}; 

2. Word Ladder II LeetCode Solution Java

public class Solution {
    int copyCounter = 0;
    public List&lt;List&lt;String&gt;&gt; findLadders(String beginWord, String endWord, List&lt;String&gt; wordList) {
    HashSet&lt;String&gt; dictionary = new HashSet&lt;String&gt;(wordList);
    List&lt;List&lt;String&gt;&gt; results = new ArrayList&lt;List&lt;String&gt;&gt;();         
    HashMap&lt;String, ArrayList&lt;String&gt;&gt; nodeNeighbors = new HashMap&lt;String, ArrayList&lt;String&gt;&gt;();
    HashMap&lt;String, Integer&gt; distance = new HashMap&lt;String, Integer&gt;();
    ArrayList&lt;String&gt; solution = new ArrayList&lt;String&gt;();
    dictionary.add(beginWord);          
    bfs(beginWord, endWord, dictionary, nodeNeighbors, distance);                 
    dfs(beginWord, endWord, nodeNeighbors, distance, solution, results);   
   return results;
}

private void bfs(String start, String end, Set&lt;String&gt; dictionary, HashMap&lt;String, ArrayList&lt;String&gt;&gt; nodeNeighbors, HashMap&lt;String, Integer&gt; distance) {
  for (String str : dictionary){
      nodeNeighbors.put(str, new ArrayList&lt;String&gt;());
  }
  Queue&lt;String&gt; queue = new LinkedList&lt;String&gt;();
  queue.offer(start);
  distance.put(start, 0);
  while (!queue.isEmpty()) {
      int count = queue.size();
      for (int i = 0; i &lt; count; i++) {
          String cur = queue.poll();
          int curDistance = distance.get(cur);       
          ArrayList&lt;String&gt; currentNodesNeighbors = getNeighbors(cur, dictionary);
          for (String neighbor : currentNodesNeighbors) {
              nodeNeighbors.get(cur).add(neighbor);
              if (!distance.containsKey(neighbor)) {
                  distance.put(neighbor, curDistance + 1);
                  if (end.equals(neighbor)){//if we have reached the end.
                      break;
                  }
                  else{
                      queue.offer(neighbor);///add neighbour for next level
                  }
              }
          }
      }
      }
  }
   
private ArrayList&lt;String&gt; getNeighbors(String node, Set&lt;String&gt; dictionary) {
  ArrayList&lt;String&gt; neighbours = new ArrayList&lt;String&gt;();
  char chs[] = node.toCharArray();
  for (char ch ='a'; ch &lt;= 'z'; ch++) {
      for (int i = 0; i &lt; chs.length; i++) {
          if(chs[i] != ch){ //if char is not the same
          char save = chs[i];
          chs[i] = ch;
          if (dictionary.contains(String.valueOf(chs))) {
              neighbours.add(String.valueOf(chs));
          }
          chs[i] = save;//Revert char back to its original char.
          }
      }

  }
  return neighbours; 
}

private void dfs(String beginWord, String endWord, HashMap&lt;String, ArrayList&lt;String&gt;&gt; nodeNeighbors, HashMap&lt;String, Integer&gt; distance, ArrayList&lt;String&gt; individualSequence, List&lt;List&lt;String&gt;&gt; results) {
    individualSequence.add(beginWord);
    if (endWord.equals(beginWord)) {
       results.add(new ArrayList&lt;String&gt;(individualSequence));
    } else {
       for (String next : nodeNeighbors.get(beginWord)) {
            if (distance.get(next) == distance.get(beginWord) + 1) {e.
                 dfs(next, endWord, nodeNeighbors, distance, individualSequence, results);
            }
        }
    }        
   individualSequence.remove(individualSequence.size() - 1);
}
}

3. Word Ladder II LeetCode Solution JavaScript

var findLadders = function(beginWord, endWord, wordList) {
    let connected = (a,b) =&gt; {
        let c = 0
        for (let i = 0; i &lt; a.length &amp;&amp; c &lt; 2; i++) {
            if (a[i] !== b[i]) c++
        }
        return c == 1
    }
    let dict = new Set(wordList);
    if (dict.has(endWord) == false) return []
    dict.delete(beginWord)
    let queue = [beginWord]
    let nodes = []
    let reached = false;    
    while (queue.length &amp;&amp; !reached) {
        nodes.push(queue.slice())
        let qlen = queue.length;
        for (let i = 0; i &lt; qlen &amp;&amp; !reached; i++) {
            let from = queue.shift();
            for (let to of dict) {                
                if (connected(from,to) == false) continue
                if (to == endWord) {
                    reached = true
                    break;
                }
                queue.push(to)                
                dict.delete(to)                
            }
        }
    }
    if (!reached) return []
    let ans = [[endWord]]
    for (let level = nodes.length - 1; level &gt;= 0; level--) {        
        let alen = ans.length
        for (let a = 0; a &lt; alen; a++) {
            let p = ans.shift()
            let last = p[0]            
            for (let word of nodes[level]) {                
                if (!connected(last, word)) continue                
                ans.push([word, ...p])
            }
        }        
    }
    return ans
}

4. Word Ladder II LeetCode Solution Python

class Solution(object):
    def findLadders(self, beginWord, endWord, wordList):
	    if not endWord or not beginWord or not wordList or endWord not in wordList \
		    or beginWord == endWord:
		    return []
	    L = len(beginWord)
	    all_combo_dict = collections.defaultdict(list)
	    for word in wordList:
		    for i in range(L):
			    all_combo_dict[word[:i] + "*" + word[i+1:]].append(word)
	    ans = []
	    queue = collections.deque()
	    queue.append((beginWord, [beginWord]))
	    visited = set([beginWord])
	    while queue and not ans:
		    length = len(queue)
		    localVisited = set()
		    for _ in range(length):
			    word, path = queue.popleft()
			    for i in range(L):
				    for nextWord in all_combo_dict[word[:i] + "*" + word[i+1:]]:
					    if nextWord == endWord:
						    ans.append(path+[endWord])
					    if nextWord not in visited:
						    localVisited.add(nextWord)
						    queue.append((nextWord, path+[nextWord]))
		    visited = visited.union(localVisited)
	    return ans
Scroll to Top