127. Word Ladder

tags: DFS, BFS, Bi-BFS
source: leetcode

Edge Cases

Solution 1 - DFS

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) return 0;
        Set<String> seen = new HashSet<>();
        seen.add(beginWord);
        return getTransTimes(beginWord, endWord, wordList, seen);
    }

    private int getTransTimes(String beginWord, String endWord, List<String> wordList, Set<String> seen) {
        if (beginWord.equals(endWord)) return 1;
        List<String> possibles = getPossibleWordsInList(beginWord, wordList);
        if (possibles.size() == 0) return 0;

        int minLength = Integer.MAX_VALUE;
        for (String word: possibles) {
            if (seen.contains(word)) continue;
            seen.add(word);
            int length = getTransTimes(word, endWord, wordList, seen);
            seen.remove(word);
            minLength = length == 0 ? minLength : Math.min(minLength, length);
        }

        return minLength == Integer.MAX_VALUE ? 0 : minLength + 1;
    }

    private List<String> getPossibleWordsInList(String word, List<String> wordList) {
        List<String> possibles = new ArrayList<String>();
        for (int i = 0; i < word.length(); i++) {
            for (int j = 0; j < 26; j++) {
                char c = (char) ('a' + j);
                if (c == word.charAt(i)) continue;
                String one = word.substring(0, i) + c + word.substring(i + 1, word.length());
                if (wordList.contains(one)) possibles.add(one);
            }
        }
        return possibles;
    }
}

Complexity

time: O(26LNN!)
space: O(N)

Solution 2 - BFS

NOTE: below is a different way to get all combinations

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) return 0;

        int L = beginWord.length();

        // get all combinations
        Map<String, List<String>> allCombs = new HashMap<>();
        wordList.forEach(
            word -> {
                for (int i = 0; i < L; i++) {
                    String wordTemplate = word.substring(0, i) + '*' + word.substring(i + 1, L);
                    List<String> combs = allCombs.getOrDefault(wordTemplate, new ArrayList<>());
                    combs.add(word);
                    allCombs.put(wordTemplate, combs);
                }
            }
        );

        int path = 1;
        Set<String> seen = new HashSet<String>();
        List<String> possibles = new LinkedList<>();
        possibles.add(beginWord);
        seen.add(beginWord);
        while (possibles.size() > 0) {
            List<String> newPossibles = new LinkedList<>();

            for (String word: possibles) {
                for (int i = 0; i < L; i++) {
                    String wordTemplate = word.substring(0, i) + '*' + word.substring(i + 1, L);
                    for (String newWord: allCombs.getOrDefault(wordTemplate, new ArrayList<>())) {
                        if (seen.contains(newWord)) continue;
                        if (newWord.equals(endWord)) {
                            return path + 1;
                        }
                        newPossibles.add(newWord);
                        seen.add(newWord);
                    }
                }
            }

            possibles = newPossibles;
            path++;
        }

        return 0;
    }
}

Complexity

time: O(L*L*N) + O(L*L*N) create allcombs: for each word, go over L times, each time use substring to create, so L^2 * M
space: O(L*L*N) each word has L templates, each template have number * L characters

Solution 3 - Bi-BFS

NOTE

wordSet here is same like seen
alwasy develop smaller side first, decrease branch numbers
the way to find combination is different, this way is better
use HashSet store list

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (beginWord == null || endWord == null || wordList == null) {
            return 0;
        }

        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) {
            return 0;
        }

        Set<String> beginQueue = new HashSet<>();
        beginQueue.add(beginWord);
        Set<String> endQueue = new HashSet<>();
        endQueue.add(endWord);
        int minLen = 1;

        while (!beginQueue.isEmpty() && !endQueue.isEmpty()) {
            if (beginQueue.size() > endQueue.size()) {
                Set<String> temp = beginQueue;
                beginQueue = endQueue;
                endQueue = temp;
            }

            Set<String> nextLevel = new HashSet<>();
            for (String curr : beginQueue) {
                char[] array = curr.toCharArray();
                for (int i = 0; i < array.length; ++i) {
                    char tmp = array[i];
                    for (char ch = 'a'; ch <= 'z'; ++ch) {
                        if (ch == tmp) {
                            continue;
                        }
                        array[i] = ch;
                        String next = String.valueOf(array);
                        if (endQueue.contains(next)) {
                            return minLen + 1;
                        }
                        if (wordSet.contains(next)) {
                            nextLevel.add(next);
                            wordSet.remove(next);
                        }
                    }
                    array[i] = tmp;
                }
            }

            beginQueue = nextLevel;
            ++minLen;
        }
        return 0;
    }
}

Complexity

time: O(LN)
space: O(LN)