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.

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

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

Solution

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.