126. Word Ladder II

hard

create nextMap by 26 letters (T = O(26NK) -> create adjList by BFS (T = O(N(N-1)) -> backtracking to get all shortest path (T = O(paths). In total, T = O(N^2). But leetcode says T = O(NK^2 + paths).

It's a directed graph, N vertex has at most (N-1) edges, K is the length of word.

Java(beat 5%)

class Solution {
    Map<String, List<String>> map = new HashMap<>();
    Map<String, List<String>> adjList = new HashMap<>();
    List<List<String>> solutions = new ArrayList<List<String>>();
    int shortest = Integer.MAX_VALUE;
    
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord)) 
            return solutions;
        
        List<String> solution = new ArrayList<String>();
        solution.add(beginWord);
        if(wordList.contains(beginWord)) {
            wordList.remove(beginWord);            
        }

        createMap(beginWord, wordList);
        System.out.println(map);
        createAdjList(beginWord, endWord);
        System.out.println(adjList);
        backtrack(beginWord, endWord, solution, new ArrayList<String>());
        return solutions;
    }

    private void createMap(String beginWord, List<String> wordList) {
        List<String> nextWord = findNext(wordList, beginWord);
        map.put(beginWord, nextWord);
        for(int i = 0; i < wordList.size(); i ++) {
            nextWord = findNext(wordList, wordList.get(i));
            map.put(wordList.get(i), nextWord);
        }
    }
    
    private List<String> findNext(List<String> wordList, String word) {
        String letters = "abcdefghijklmnopqrstuvwxyz";
        List<String> next = new ArrayList<>();
        for(int i = 0; i < word.length(); i ++) {
            for(int j = 0; j < letters.length(); j ++) {
                String newWord = word.substring(0, i) + letters.charAt(j) + word.substring(i+1, word.length());
                if(!newWord.equals(word) && wordList.contains(newWord))
                    next.add(newWord);
            }
        }
        return next;
    }
    
    private void createAdjList(String beginWord, String endWord) {
        Queue<String> q = new LinkedList<String>();
        q.add(beginWord);
        Map<String, Integer> visited = new HashMap<String, Integer>();
        int layer = 0;
        while(q.size() > 0) {
            int l = q.size();
            for(int i = 0; i < l; i++) {
                String currWord = q.poll();  
                adjList.put(currWord, new ArrayList<String>());
                List<String> next = map.get(currWord);
                for(String s: next) {
                    if(visited.containsKey(s) && visited.get(s) != layer)
                        continue;
                    visited.put(s, layer);
                    adjList.get(currWord).add(s);
                    q.add(s);
                }
            }
            layer ++;
        }
    }
    
    private void backtrack(String beginWord, String endWord, List<String> solution, List<String> visited) {
        // stop condition
        if(solution.contains(endWord)) {
            if(solution.size() < shortest) {
                solutions.clear();
                solutions.add(new ArrayList<String>(solution));
                shortest = solution.size();
            } else if(solution.size() == shortest)
                solutions.add(new ArrayList<String>(solution));
            return;
        }
        
        // regular case
        for(String next: adjList.get(beginWord)) {
            if(!visited.contains(next) && solution.size() < shortest) {
                solution.add(next);
                visited.add(next);
                backtrack(next, endWord, solution, visited);
                solution.remove(next);
                visited.remove(next);
            }
        }
    }
}

Second Tab