My accepted java solution with DAG


  • 0
    1. Build a simple DAG (Directed acyclic graph) with a BFS.
      a. Maintain two HashMaps. One to build a graph (graph) and other one to maintain a minimum distance (minDistance) to each node starting from 'beginWord'. 'beginWord' always starts with distance 0.
      b. Start bfs from a begin node (currWord), explore each node (iterate through each characters from a-z), you can call this 'child' node and add this as a connection in the graph and include this in the queue if and only if the child node is present in the dictionary and has never been reached before and is not equal to the endWord. The reason for not including the endWord in queue is that we would not want to continue further once the final destination has been reached. If the child has been reached before and the minDistance to the child node is same as current distance then simply add this as a connection in the graph.
      c. Continue until the queue is empty and the resultant graph would be a DAG.
    1. Do a full recursive DFS on the DAG that was constructed above to build the path and return the result.
    public class Solution 
    {
    
        private Queue<String> queue = new ArrayDeque<>();
        private Set<String> dictionary = new HashSet<>();
        private static final String CONST = "abcdefghijklmnopqrstuvwxyz";
        private Map<String, Set<String>> graph = new HashMap<>();
        private Map<String, Integer> minDistance = new HashMap<>();
        private List<List<String>> result = new ArrayList<>();
        
        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) 
        {
            dictionary.addAll(wordList);
            bfs(beginWord, endWord, wordList);
            List<String> path = new ArrayList<>();
            path.add(beginWord);
            dfs(beginWord, endWord, path);
            return result;
        }
        
            /**
         * Bfs
         * @param beginWord begin word
         * @param endWord end word
         * @param wordList wordlist
         */
        private void bfs(String beginWord, String endWord, List<String> wordList)
        {
            queue.offer(beginWord);
            minDistance.put(beginWord, 0);
            while(!queue.isEmpty())
            {
                String currWord = queue.poll();
                StringBuilder childSb = new StringBuilder(currWord);
                for(int j = 0, ln = childSb.length(); j < ln; j ++ )
                {
                    for(int i = 0, l = CONST.length(); i < l; i ++ )
                    {
                        char old = childSb.charAt(j);
                        childSb.replace(j, j + 1, String.valueOf(CONST.charAt(i)));
                        String child = childSb.toString();
                        if(dictionary.contains(child))
                        {
                            if(minDistance.get(child) == null)
                            {
                                minDistance.put(child, minDistance.get(currWord) + 1);
                                addChild(currWord, child);
                                if(!child.equals(endWord))
                                    queue.offer(child);
                            }
                            else
                            {
                                if(minDistance.get(child) == (minDistance.get(currWord) + 1))
                                    addChild(currWord, child);
                            }
                        }
                        childSb.replace(j, j + 1, String.valueOf(old));
                    }
                }
            }
        }
        
            /**
         * Add child
         * @param parent parent
         * @param child child
         */
        private void addChild(String parent, String child)
        {
            Set<String> children = graph.get(parent);
            if(children == null)
                children = new HashSet<>();
            children.add(child);
            graph.put(parent, children);
        }
    
        /**
         * Dfs to build path
         * @param currWord node
         * @param endWord endword
         * @param path path
         */
        private void dfs(String currWord, String endWord, List<String> path)
        {
            if(currWord.equals(endWord))
            {
                result.add(new ArrayList<>(path));
            }
            else
            {
                Set<String> children = graph.get(currWord);
                if(children != null)
                {
                    for(String c : children)
                    {
                        path.add(c);
                        dfs(c, endWord, path);
                        path.remove(path.size() - 1);
                    }
                }
            }
        }
    }
    

Log in to reply
 

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