Grokking Graph Algorithms for Coding Interviews

0% completed

​

Word Ladder (hard)

Problem Statement

A transformation sequence is a sequence that starts from the word beginWord, ends with endWord, and contains a word from the given dictionary wordList in the middle i.e. a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Each adjacent pair of words differs by a single letter.
  • Each si for 1 <= i <= k is in wordList. sk == endWord
  • The beginWord does not need to be in wordList.

Given two strings, beginWord and endWord, and a `wordList

.....

.....

.....

Like the course? Get enrolled and start learning!
The Whiz

The Whiz

· a year ago

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    queue.offer(beginWord);
    int dist = 1;

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String current = queue.poll();
            if (current.equals(endWord)) {
                return dist;
            }
            for (String word : wordList) {
                if (!visited.contains(word) && canForm(word, current)) {
                    queue.offer(word);
                    visited.add(word);
                }
            }
        }
        dist++;
    }
    return -1;
}

private boolean canForm(String word, String current) {
    if (