Modified BFS


  • 0
    Z

    Using normal bfs, we could easily find the shortest path. However, mark a node instantly after pushing it into the queue could harm us from finding all the shortest paths! Instead, think that bfs partitions all the words into different 'levels'/'layers'according to their distance from beginWord. The current word A (currently polled from the queue) could points to the next word B if and only if B is not visited or dist(B,beginWord) = dist(A,beginWord) + 1.

    We could use Map<String, Integer> vis memorizing in which level\layer the word lies in. If a word is not visited so far, vis[word] = -1.

    There could be exponential number of shortest paths, thus time complexity could be that high.

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            /* modified bfs
            *  in the normal bfs, we mark the word as visited instantly after pushing it into the queue,
            *  which prevent us from finding all the shortest paths. Instead, think that bfs partitions
            *  all the words into different 'levels'/'layers' according to their distance from beginWord.
            *  The current word A (currently polled from the queue) could points to the next word B if 
            *  and only if B is not visited or dist(B,beginWord) = dist(A,beginWord) + 1.
            */
            
            // vis[word]: in which level does word lies in, if not visited, vis[word]=-1
            Map<String, Integer> vis = new HashMap<>();
            // root node
            vis.put(beginWord, 0);
            for (String word: wordList) vis.put(word, -1);
            
            // parent[word]: the direct parent word pointing to the current word
            Map<String, List<String>> parent = new HashMap<>();
            
            Queue<String> q = new LinkedList<>();
            q.offer(beginWord);
            
            String cur = "";
            int level = 0;
            while (!q.isEmpty()) {
                cur = q.poll();
                level = vis.get(cur);
                if (cur.equals(endWord)) break;
                for (int i=0; i<cur.length(); i++) {
                    for (char c='a'; c<='z'; c++) {
                        String mutated = cur.substring(0,i) + c + cur.substring(i+1,cur.length());
                        if (!vis.containsKey(mutated)) continue;
                        int level_of_mutated = vis.get(mutated);
                        if (level_of_mutated==-1) {
                            q.offer(mutated);
                            vis.put(mutated, level+1);
                            if (!parent.containsKey(mutated)) parent.put(mutated, new LinkedList<String>());
                            parent.get(mutated).add(cur);
                        }
                        else if (level_of_mutated==level+1) {
                            //if (!parent.containsKey(mutated)) parent.put(mutated, new LinkedList<String>());
                            parent.get(mutated).add(cur);
                        }
                    }
                }
            }
            
            // extract paths
            List<List<String>> ans = new LinkedList<List<String>>();
            dfs(endWord, beginWord, parent, new LinkedList<String>(), ans);
            return ans;
        }
        
        public void dfs(String word, String beginWord, Map<String, List<String>>parent, List<String> path, List<List<String>> ans) {
            path.add(0, word);
            if (word.equals(beginWord)) {
                ans.add(new LinkedList<String>(path));
                path.remove(0);
                return;
            }
            if (parent.containsKey(word)) {
                for (String pa: parent.get(word)) {
                    dfs(pa, beginWord, parent, path, ans);
                }
            }
            // traceback
            path.remove(0);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.