Word Ladder

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s<sub>1</sub> -> s<sub>2</sub> -> ... -> s<sub>k</sub> such that:

• Every adjacent pair of words differs by a single letter.

• Every s<sub>i</sub> for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.

• s<sub>k</sub> == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

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

Constraints:

• 1 <= beginWord.length <= 10

• 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 words in wordList are unique.

Solution

Idea: We start with the beginning word and change each character, one at a time, to every letter in the alphabet. We check if the new word is in the list of allowed words, and if it is, we move to that word until we reach the endWord.

We use BFS because it helps us find the level at which we reach the endWord.

Note:

• We put all the allowed words into a set and remove them once we use them in our iterations to avoid duplicate combinations.

• If calculating the breadth becomes complex, it's better to use a pair that stores both the string and the current breadth. Place this pair in a queue and use it for the next calculation.

Time - O(n)

Space - O(n)

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new ArrayDeque<>();
        Set<String> set = new HashSet<>();

        boolean isEndWordPresent = false;
        for(String word: wordList){
            set.add(word);
            if(word.equals(endWord)) isEndWordPresent=true;
        }
        if(!isEndWordPresent) return 0;

        int breadth = 1;
        if(set.contains(beginWord)) {
            set.remove(beginWord);
        }

        queue.add(beginWord);
        while(!queue.isEmpty()){
            int size = queue.size();
            System.out.println(queue);
            for(int z=0; z<size; z++){
                String word = queue.poll();

                for(int position=0; position<word.length(); position++){
                    //Add all possible words
                    char[] chars = word.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        // String possibleWord = insertAtIndex(c, word, position);
                        chars[position] = c;
                        String possibleWord = new String(chars);
                        if(possibleWord.equals(endWord)) return breadth+1;
                        if(set.contains(possibleWord)){
                            queue.add(possibleWord);
                            set.remove(possibleWord);
                        }
                    }
                }
            }
            breadth+=1; 
        }

        return 0;
    }

    private String insertAtIndex(Character c, String word, int index){
        return word.substring(0, index) + c + word.substring(index+1);
    }
}