Java: Word Ladder

Thought Process

The solution uses Breadth-First Search (BFS) to find the shortest transformation sequence. We start from the beginWord and explore all possible one-letter transformations at each level. Each transformation is checked against the word dictionary and marked as visited to avoid cycles. The key optimization is processing words level by level, which guarantees the shortest path is found first. Furthermore, we maintain a counter to track the number of transformations required to reach the target word, which will become our final answer. 

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        

        Set<String> wordSet = new HashSet<>(wordList);
        Queue<String> qu = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        if(!wordSet.contains(endWord))
            return 0;

        qu.offer(beginWord);
        visited.add(beginWord);
        int changes = 1;

        while(!qu.isEmpty()){

            int sz = qu.size();
            System.out.println(qu);
            for(int i=0;i<sz;i++){

                String word = qu.poll();
                if(word.equals(endWord))
                    return changes;

                for(int j=0;j<word.length();j++){

                    for(char ch = 'a';ch<='z';ch++){

                        char[] wordArray = word.toCharArray();
                        wordArray[j]=ch;
                        String str = new String(wordArray);
                        if(wordSet.contains(str) && !visited.contains(str)){

                            qu.offer(str);
                            visited.add(str);
                        }
                    }
                } 
            }
            changes++;
        }
        return 0;
    }
}

Code Complexity

Time Complexity: O(M2×N)

Where 'M' is word length and 'N' is dictionary size. For each word, we check 'M' characters and 26 possible transformations.

Space Complexity: O(N)

We store the dictionary and visited words, both requiring space proportional to the number of words.

Code copied!