127. Word Ladder

/**

 * 127. 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 si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.

 * sk == 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.

 */

See solution of the problem on github at: https://github.com/zcoderz/leetcode/blob/main/src/main/java/trees/wordladder/WordLadderEfficient.java

Observations:

  1. You can find list of words that are different in only one character by
    1. For each character in the word replacing that character with another character such as “*” and mapping given word as one of the transformations for the word with the “*”
    1. Then finding list of words that map to the given transformed word that contained “*” via a map lookup
  2.  You can run a BFS search from start word until you find the end word
  3.  A single directional BFS will traverse several unneeded paths, you can have a more focused search path if you run BFS from first word and another from the last word until you find a match.

Algorithm:

  1. As observed above, for each word that maps to a given word with once char replaced
    1. Run a bfs from start word to the end word
    1. And another bfs from end word to start word
  2. Create a map of strings visited for start and end directions to avoid cycles
  3. Use the same map as in 2 to also store the level of traversal
  4. Each time you traverse further search for the new word in opposite map
    1. If found then current level + opposite level is the shortest transformation sequence

Here is the code snippet to map group of words that are single character apart:

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Map<String, List<String>> wordMappings = new HashMap<>();
    boolean matchEnd = false;
    //words can connect if they are only one char apart at most - i,e hit can connect with hot and pit
    //hence we can match by replacing each char in string one by one with * and creating mapping to original string
    //and storing this mapping in a map with key as modified word and value as list of words that map the modified
    //word
    for (String word : wordList) {
        for (int i = 0; i < word.length(); i++) {
            String modWord = word.substring(0, i) + "*" + word.substring(i + 1);
            List<String> words = wordMappings.computeIfAbsent(modWord, (l) -> new ArrayList<>());
            words.add(word);
        }
..........

Here is the code snippet for the BFS traversal:

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    ........
    //here is the BFS bi directional loop
    while (!leftQueue.isEmpty() || !rightQueue.isEmpty()) {
        Pair<String, Integer> lVal = leftQueue.poll();
        if (lVal != null) {
            for (int i = 0; i < lVal.first.length(); i++) {
                String modWord = lVal.first.substring(0, i) + "*" + lVal.first.substring(i + 1);
                List<String> mappings = wordMappings.get(modWord);
                if (mappings == null) continue;
                for (String word : mappings) {
                    if (leftVisited.containsKey(word)) {
                        continue;
                    }
                    Integer level = rightVisited.get(word);
                    if (level != null) {
                        return lVal.second + level;
                    }
                    leftVisited.put(word, lVal.second + 1);
                    leftQueue.add(new Pair<>(word, lVal.second + 1));
                }
            }
        }

        Pair<String, Integer> rVal = rightQueue.poll();
        if (rVal != null) {
            for (int i = 0; i < rVal.first.length(); i++) {
                String modWord = rVal.first.substring(0, i) + "*" + rVal.first.substring(i + 1);
                List<String> mappings = wordMappings.get(modWord);
                if (mappings == null) continue;
                for (String word : mappings) {
                    if (rightVisited.containsKey(word)) {
                        continue;
                    }
                    Integer level = leftVisited.get(word);
                    if (level != null) {
                        return rVal.second + level;
                    }
                    rightVisited.put(word, rVal.second + 1);
                    rightQueue.add(new Pair<>(word, rVal.second + 1));
                }
            }
        }
    }
    return 0;
}