304 North Cardinal St.
Dorchester Center, MA 02124

# Word Ladder II LeetCode Solution

## Problem – Word Ladder II LeetCode Solution

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`.

## Word Ladder II LeetCode Solution in C++

``````    vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
//very interesting problem
//It can be solved with standard BFS. The tricky idea is doing BFS of paths instead of words!
//Then the queue becomes a queue of paths.
vector<vector<string>> ans;
queue<vector<string>> paths;
wordList.insert(endWord);
paths.push({beginWord});
int level = 1;
int minLevel = INT_MAX;

//"visited" records all the visited nodes on this level
//these words will never be visited again after this level
//and should be removed from wordList. This is guaranteed
// by the shortest path.
unordered_set<string> visited;

while (!paths.empty()) {
vector<string> path = paths.front();
paths.pop();
if (path.size() > level) {
//reach a new level
for (string w : visited) wordList.erase(w);
visited.clear();
if (path.size() > minLevel)
break;
else
level = path.size();
}
string last = path.back();
//find next words in wordList by changing
//each element from 'a' to 'z'
for (int i = 0; i < last.size(); ++i) {
string news = last;
for (char c = 'a'; c <= 'z'; ++c) {
news[i] = c;
if (wordList.find(news) != wordList.end()) {
//next word is in wordList
//append this word to path
//path will be reused in the loop
//so copy a new path
vector<string> newpath = path;
newpath.push_back(news);
visited.insert(news);
if (news == endWord) {
minLevel = level;
ans.push_back(newpath);
}
else
paths.push(newpath);
}
}
}
}
return ans;
}
``````

## Word Ladder II LeetCode Solution in Java

``````public List<List<String>> findLadders(String start, String end, List<String> wordList) {
HashSet<String> dict = new HashSet<String>(wordList);
List<List<String>> res = new ArrayList<List<String>>();
HashMap<String, ArrayList<String>> nodeNeighbors = new HashMap<String, ArrayList<String>>();// Neighbors for every node
HashMap<String, Integer> distance = new HashMap<String, Integer>();// Distance of every node from the start node
ArrayList<String> solution = new ArrayList<String>();

bfs(start, end, dict, nodeNeighbors, distance);
dfs(start, end, dict, nodeNeighbors, distance, solution, res);
return res;
}

// BFS: Trace every node's distance from the start node (level by level).
private void bfs(String start, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance) {
for (String str : dict)
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();
boolean foundEnd = false;
for (int i = 0; i < count; i++) {
String cur = queue.poll();
int curDistance = distance.get(cur);
ArrayList<String> neighbors = getNeighbors(cur, dict);

for (String neighbor : neighbors) {
if (!distance.containsKey(neighbor)) {// Check if visited
distance.put(neighbor, curDistance + 1);
if (end.equals(neighbor))// Found the shortest path
foundEnd = true;
else
queue.offer(neighbor);
}
}
}

if (foundEnd)
break;
}
}

// Find all next level nodes.
private ArrayList<String> getNeighbors(String node, Set<String> dict) {
ArrayList<String> res = 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) continue;
char old_ch = chs[i];
chs[i] = ch;
if (dict.contains(String.valueOf(chs))) {
}
chs[i] = old_ch;
}

}
return res;
}

// DFS: output all paths with the shortest distance.
private void dfs(String cur, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance, ArrayList<String> solution, List<List<String>> res) {
if (end.equals(cur)) {
} else {
for (String next : nodeNeighbors.get(cur)) {
if (distance.get(next) == distance.get(cur) + 1) {
dfs(next, end, dict, nodeNeighbors, distance, solution, res);
}
}
}
solution.remove(solution.size() - 1);
}
``````

## Word Ladder II LeetCode Solution in Python

``````class Solution(object):
def findLadders(self, beginWord, endWord, wordList):

wordList = set(wordList)
res = []
layer = {}
layer[beginWord] = [[beginWord]]

while layer:
newlayer = collections.defaultdict(list)
for w in layer:
if w == endWord:
res.extend(k for k in layer[w])
else:
for i in range(len(w)):
for c in 'abcdefghijklmnopqrstuvwxyz':
neww = w[:i]+c+w[i+1:]
if neww in wordList:
newlayer[neww]+=[j+[neww] for j in layer[w]]

wordList -= set(newlayer.keys())
layer = newlayer

return res
``````
##### Word Ladder II LeetCode Solution Review:

In our experience, we suggest you solve this Word Ladder II LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Word Ladder II LeetCode Solution

Find on Leetcode

##### Conclusion:

I hope this Word Ladder II LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions