LeetCode 127. Word Ladder

Problem:

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWordto endWord, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

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

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Solution:

Today I knew that building an adjacency map is a stupid, stupid solution when you have way more elements than path.

public class Solution {
    
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        wordList.add(endWord);
        Queue<String> current = new LinkedList<String>();
        int step = 1;
        current.offer(beginWord);
        while (!current.isEmpty()) {
            int size = current.size();
            while (size > 0) {
                String word = current.poll();
                if (word.equals(endWord))
                    return step;
                for (int i = 0; i < word.length(); i++) {
                    char[] arr = word.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        arr[i] = c;
                        String check = new String(arr);
                        if (!check.equals(word) && wordList.contains(check)) {
                            current.offer(check);
                            wordList.remove(check);
                        }
                    }
                }
                size--;
            }
            step++;
        }
        return 0;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *