LeetCode: Word Ladder ( Well Commented solution)

 The Question statement is copy pasted from leet code as it is:

Given two words beginWord and endWord, and a dictionary wordList, return the length of the shortest transformation sequence from beginWord to endWord, such that:

• Only one letter can be changed at a time.
• Each transformed word must exist in the word list.

Return 0 if there is no such transformation sequence.

 

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

 

Constraints:

• 1 <= beginWord.length <= 100
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All the strings in wordList are unique.

My Solution :

package madwani.sushil.leetcode.Jan_8_15_2021;

import java.util.*;

public class WordLadder {
    public static void main(String[] args) {
        String[] wordList = new String[] {"a","b","c"};
        String beginWord = "a";
        String endWord =  "c";
        String[] wordList1 = new String[] { "hot","dot","dog","lot","log","cog" };
        String beginWord1 = "hit";
        String endWord1 =  "cog";
        String[] wordList2 = new String[] { "hot","dog"};
        String beginWord2 = "hot";
        String endWord2 =  "dog";
        System.out.println(ladderLength1(beginWord, endWord, Arrays.asList(wordList))); // 2
        System.out.println(ladderLength1(beginWord1, endWord1, Arrays.asList(wordList1))); // 5
        System.out.println(ladderLength1(beginWord2, endWord2, Arrays.asList(wordList2))); // 1
    }
    // we are using Breadth First Search to find the shortest word transformation
    // time complexity is O (wordList size * wordLength * wordLength) - explained at each step
    public static int ladderLength1(String beginWord, String endWord, List<String> wordList) {
        Set<String> words = new HashSet<>(wordList);
        if (!words.contains(endWord)) return 0;
        // we will use queue to track the levels as we move ahead to find the end word
        Queue<String> wordQueue = new LinkedList<>();
        wordQueue.add(beginWord);

        // visited set is maintained for string already visited and counted
        Set<String> visited = new HashSet<>();

        // as we already added the begin word in it, so we are at level of search
        int level = 1;
        //visited.add(beginWord);
        while (!wordQueue.isEmpty()) { // the time complexity of this operation would be O(input word list size)
            // now lets go deep inside at each level
            // every level contain words which have 1 char from previous level
            // as we are going for next level, lets increase the level
            level++;
            int size = wordQueue.size();
            // we need to work on all words on that level
            while(size-- > 0) {
                String wordToSearch = wordQueue.poll();
                // below will add it to visited queue and run the algo
                // if already exist it will ignore that word and won't run the algo
                if (visited.add(wordToSearch)) {
                    // major work is happening here
                    // we are trying to make all possible combination of the word
                    for (int i=0; i < wordToSearch.length(); i++) { // here the time complexity is O(length of the word)
                        char[] chars = wordToSearch.toCharArray();
                        char[] temp = wordToSearch.toCharArray();
                        for (char ch = 'a'; ch <= 'z'; ch++) {
                            if (ch == chars[i]) continue;
                            temp[i] = ch;
                            String str = new String(temp);
                            // if that combination is part of the input word list
                            if (words.contains(str)) {
                                // and if that is the end word, we are done
                                if (str.equals(endWord)) return level; // the comparision time complexity is O(length of the word)
                                // else add that into the queue for the next level search
                                wordQueue.add(str);
                            }
                        }
                    } // this loop will be having time complexity of O(wordlength * wordlength)
                }
            }
        } // this loop total time complexity would be O(listsize * wordLength * wordlength)
        return 0;
    }
}