Last updated on January 14th, 2025 at 06:17 am
Here, we see a Word Ladder II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
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
1. 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.
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Graph Traversal. Specifically, the problem involves Breadth-First Search (BFS) for finding the shortest path in an unweighted graph and Depth-First Search (DFS) for backtracking to construct all possible paths. This pattern is commonly used in problems involving shortest paths, word ladders, and transformations.
3. Code Implementation in Different Languages
3.1 Word Ladder II 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;
}
};
3.2 Word Ladder II 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.3 Word Ladder II 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
}
3.4 Word Ladder II 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
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(N² * M) | O(N² * NM) |
| Java | O(N² * M) | O(N² * NM) |
| JavaScript | O(N² * M) | O(N² * NM) |
| Python | O(N² * M) | O(N² * NM) |
where N is the number of words and M is the word length.