# Word Ladder II

This page explains Java solution to problem `Word Ladder II` using `Dijkstra's` algorithm.

## Problem Statement

Given two words `beginWord` and `endWord`, and a dictionary's word list, find all shortest transformation sequence(s) from `beginWord` to `endWord`, such that:

• 1. Only one letter can be changed at a time.
• 2. Each transformed word must exist in the word list. Note that `beginWord` is not a transformed word.
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"]
]

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: []

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class WordLadderIi {
private HashMap<String, HashSet<String>> graph = new HashMap<>();
private List<List<String>> res = new ArrayList<>();

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
HashMap<String, Integer> distance = new HashMap<>();
for(String word: wordList) distance.put(word, Integer.MAX_VALUE);
distance.put(beginWord, 0);

if(!distance.containsKey(endWord)) return res;

Queue<String> q = new LinkedList<>();
q.offer(beginWord);
while(!q.isEmpty()) {
String word = q.poll();
for(int i = 0; i < word.length(); i++) {
for(char ch = 'a'; ch <= 'z'; ch++) {
if(word.charAt(i) != ch) {
String newWord = word.substring(0, i) + ch + (i + 1 < word.length() ? word.substring(i + 1) : "");
if(distance.containsKey(newWord) && distance.get(newWord) >= distance.get(word) + 1) {
distance.put(newWord, distance.get(word) + 1);
HashSet<String> list = graph.getOrDefault(word, new HashSet<>());
list.add(newWord);
graph.put(word, list);
q.offer(newWord);
}
}
}
}
}

dfs(beginWord, endWord, new ArrayList<>());
return res;
}

private void dfs(String beginWord, String endWord, List<String> ladder) {
if(beginWord.equals(endWord)) {
ladder.add(endWord);
res.add(new ArrayList<>(ladder));
ladder.remove(ladder.size() - 1);
}
else {
ladder.add(beginWord);
if(graph.containsKey(beginWord)) {
for(String word: graph.get(beginWord)) {
dfs(word, endWord, ladder);
}
}
ladder.remove(ladder.size() - 1);
}
}
}
``````

## Time Complexity

Total Time complexity = O(V * W * 26) + O(V + E)

O(V * W * 26) Where
V is total number of Vertices, in our case elements in an input array words.
W is length of word in an input array words.
26 because we iterate over all the elements from 'a' to 'z'

O(V + E) Where
V is total number of Vertices, in our case elements in an input array words.
E is total number of Edges, in our case connections that we generate in a graph variable.

## Space Complexity

O(V + E) Where
V is total number of Vertices, in our case elements in an input array words.
E is total number of Edges, in our case connections that we generate in a graph variable.