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

Word Ladder II LeetCode Solution

Problem Statement

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.

1. Word Ladder II LeetCode Solution C++

class Solution {
public:
bool able(string s,string t){
    int c=0;
    for(int i=0;i<s.length();i++)
        c+=(s[i]!=t[i]);
    return c==1;
}
void bfs(vector<vector<int>> &g,vector<int> parent[],int n,int start,int end){
    vector <int> dist(n,1005);
    queue <int> 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]>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<vector<int>> &Paths, vector<int> &path, vector<int> 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<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
    int n=wordList.size(),start=-1,end=-1;
    vector<vector<string>> ANS;
    for(int i=0;i<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<vector<int>> g(n,vector<int>()),Paths;
    vector<int> parent[n],path;
    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<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 <string> now;
        for(int i=0;i<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<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    HashSet<String> dictionary = new HashSet<String>(wordList);
    List<List<String>> results = new ArrayList<List<String>>();         
    HashMap<String, ArrayList<String>> nodeNeighbors = new HashMap<String, ArrayList<String>>();
    HashMap<String, Integer> distance = new HashMap<String, Integer>();
    ArrayList<String> solution = new ArrayList<String>();
    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<String> dictionary, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance) {
  for (String str : dictionary){
      nodeNeighbors.put(str, new ArrayList<String>());
  }
  Queue<String> queue = new LinkedList<String>();
  queue.offer(start);
  distance.put(start, 0);
  while (!queue.isEmpty()) {
      int count = queue.size();
      for (int i = 0; i < count; i++) {
          String cur = queue.poll();
          int curDistance = distance.get(cur);       
          ArrayList<String> 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<String> getNeighbors(String node, Set<String> dictionary) {
  ArrayList<String> neighbours = new ArrayList<String>();
  char chs[] = node.toCharArray();
  for (char ch ='a'; ch <= 'z'; ch++) {
      for (int i = 0; i < 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<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance, ArrayList<String> individualSequence, List<List<String>> results) {
    individualSequence.add(beginWord);
    if (endWord.equals(beginWord)) {
       results.add(new ArrayList<String>(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) => {
        let c = 0
        for (let i = 0; i < a.length && c < 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 && !reached) {
        nodes.push(queue.slice())
        let qlen = queue.length;
        for (let i = 0; i < qlen && !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 >= 0; level--) {        
        let alen = ans.length
        for (let a = 0; a < 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