Skip to main content

Word Ladder

Word Ladder: A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every s_i for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • s_k == 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.

Try this Problem on your own or check similar problems:

  1. Minimum Genetic Mutation
  2. Words Within Two Edits of Dictionary
  3. Word Ladder II
Solution:​
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> s = new HashSet<>(wordList);
    if(!s.contains(endWord)) return 0;

    Queue<String> q = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    q.add(beginWord);
    visited.add(beginWord);

    int level = 1;

    while(!q.isEmpty()){
        int size = q.size();
        while(size-->0){
            String word = q.poll();
            if(word.equals(endWord)) return level;

            for(int j = 0; j < word.length(); ++j){
                for(char l = 'a'; l <= 'z'; ++l){
                    char wordArr[] = word.toCharArray();
                    wordArr[j] = l;

                    String modifiedWord = new String(wordArr);
                    if(s.contains(modifiedWord) && !visited.contains(modifiedWord)){
                        q.add(modifiedWord);
                        visited.add(modifiedWord);
                    }
                }
            }
        }
        ++level;
    }
    return 0;
}
Time/Space Complexity:​
  • Time Complexity: O(m^2 * n)
  • Space Complexity: O(mn)
Explanation:​

To find the shortest path we could build a graph where each word is a vertex and there exists an edge between words only if they differ by maximum one letter. If we insert the beginWord in the graph if it doesn't already exist, to find the shortest path in the graph we can use BFS since it finds the shortest path between a source and destination vertex in unweighted graph (each edge is of the same weight here). The algorithm is straightforward:

class Solution {
    private class Graph{
        Set<Integer>[] graph;
        int numberOfNodes;

        public Graph(int numberOfNodes){
            this.numberOfNodes = numberOfNodes;
            graph = new Set[numberOfNodes];
            for(int i = 0;  i < numberOfNodes; ++i) graph[i] = new HashSet<>();
        }

        public void buildGraph(List<String> wordList){
            for(int i = 0; i < wordList.size(); ++i){
                for(int j = 0; j < wordList.size(); ++j){
                    if(i != j && diffByOne(wordList.get(i), wordList.get(j))){
                        graph[i].add(j);
                        graph[j].add(i);
                    }
                }
            }
        }

        private boolean diffByOne(String word1, String word2){
            int diff = 0;
            for(int i = 0; i < word1.length(); ++i){
                if(word1.charAt(i) != word2.charAt(i)) ++diff;
                if(diff > 1) return false;
            }
            return true;
        }

        private int bfs(int source, int destination){
            Queue<Integer> q = new LinkedList<>();
            boolean[] visited = new boolean[numberOfNodes];

            q.add(source);
            int level = 1;

            while(!q.isEmpty()){
                int size = q.size();
                while(size-->0){
                    int v = q.poll();
                    visited[v] = true;
                    Set<Integer> neighbors = graph[v];
                    for(int neighbor : neighbors){
                        if(!visited[neighbor]){
                            q.add(neighbor);
                            if(neighbor == destination) return level;
                        }
                    }
                }
                ++level;
            }

            return numberOfNodes + 1;
        }
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Map<String, Integer> wordToIdx = new HashMap<>();
        for(int i = 0; i < wordList.size(); ++i){
            wordToIdx.put(wordList.get(i), i);
        }

        if(!wordToIdx.containsKey(endWord)) return 0;
        if(!wordToIdx.containsKey(beginWord)){
            wordList.add(beginWord);
            wordToIdx.put(beginWord, wordList.size() - 1);
        }
        Graph g = new Graph(wordList.size());
        g.buildGraph(wordList);
        int minDistance = g.bfs(wordToIdx.get(beginWord), wordToIdx.get(endWord)) + 1;
        return minDistance > wordList.size() ? 0 : minDistance;
    }
}

But notices that we spend O(l * n^2) (where l is the wordLength) for building the graph, we can cut this by implicitly building the graph starting from the beginWord and checking if any letter modification leads to another word in the wordList. The same BFS logic applies here, we just don't build the graph. The space complexity is O(mn) since we can store at maximum n the length of the wordList words with length of m (m == l == wordLength). The time complexity is O(m^2 * n) since we traverse over n words and for each word we iterate over m characters (length of words in wordList) each time trying to create a modifiedWord which needs to be hashed (checking if it exists in set, converting to array of character taking O(m) time) leading to O(m^2) per traversal.

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> s = new HashSet<>(wordList);
    if(!s.contains(endWord)) return 0;

    Queue<String> q = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    q.add(beginWord);
    visited.add(beginWord);

    int level = 1;

    while(!q.isEmpty()){
        int size = q.size();
        while(size-->0){
            String word = q.poll();
            if(word.equals(endWord)) return level;

            for(int j = 0; j < word.length(); ++j){
                for(char l = 'a'; l <= 'z'; ++l){
                    char wordArr[] = word.toCharArray();
                    wordArr[j] = l;

                    String modifiedWord = new String(wordArr);
                    if(s.contains(modifiedWord) && !visited.contains(modifiedWord)){
                        q.add(modifiedWord);
                        visited.add(modifiedWord);
                    }
                }
            }
        }
        ++level;
    }
    return 0;
}