Last updated on July 20th, 2024 at 04:20 am
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
Table of Contents
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
sifor1 <= i <= kis inwordList. Note thatbeginWorddoes not need to be inwordList. 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