263ms Easy to Understand Java Solution Using Simple BFS


  • 0
    S

    Inspired by Share two similar Java solution that Accptted by OJ.
    In order to get the shortest transformations, we can build a graph and then bfs the graph until we get to the level where the endWord first appears. All the paths from the beginWord to this level are shortest.

    The solution is quite simple, we build a graph by bfs to the level where the endWord appears. After we scan all the nodes at this level, we could build all the paths with the graph we built.

    
    
    public class Solution {
        Set<String> getOneEditWord(String word, Set<String> dict) {
            Set<String> result = new HashSet();
            for (int i = 0; i < word.length(); i++) {
                for (char j = 'a'; j <= 'z'; j++) {
                    if (j == word.charAt(i)) continue; // itself
                    StringBuilder w = new StringBuilder(word);
                    w.setCharAt(i, j);
                    String nn = w.toString();
                    if (dict.contains(nn)) result.add(nn);
                }
            }
            return result;
        }
    
        public void backTrace(Map<String, Set<String>> graph, List<List<String>> result, String start, String end, Deque<String> curPath) {
            if (end.equals(start)) {
                LinkedList<String> list = new LinkedList<>(curPath);
                result.add(list);
                return;
            }
    
            if (null == graph.get(start)) {
                return;
            }
    
            for (String child : graph.get(start)) {
                curPath.addLast(child);
                backtrace(graph, result, child, end, curPath);
                curPath.removeLast();
            }
        }
    
        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            Map<String, Set<String>> graph = new HashMap();
            Queue<String> toVisit = new ArrayDeque<>();
            Map<String, Integer> ladder = new HashMap();
    
            Set<String> dict = new HashSet<>();
            dict.addAll(wordList);
    
            int step = 0;
            ladder.put(beginWord, step);
            toVisit.add(beginWord);
            int minStep = Integer.MAX_VALUE;
    
            while (!toVisit.isEmpty()) {
                String word = toVisit.poll();
                step = ladder.get(word) + 1;
                if (step > minStep) break; // the shorttest has been processed
                for (String child : getOneEditWord(word, dict)) {
                    //System.out.println(child);
                    int cStep = ladder.getOrDefault(child, Integer.MAX_VALUE);
                    if (cStep < step) continue;
                    if (cStep > step) {
                        ladder.put(child, step);
                        toVisit.add(child);
                    }
                    if (graph.containsKey(word)) {
                        graph.get(word).add(child);
                    } else {
                        Set<String> set = new HashSet<>();
                        set.add(child);
                        graph.put(word, set);
                    }
                    if (child.equals(endWord)) {
                        if (minStep > step) {
                            minStep = step;
                        }
                    }
                }
            }
            //System.out.println(graph);
            List<List<String>> result = new LinkedList<>();
            Deque<String> bPath = new ArrayDeque<>();
            bPath.add(beginWord);
            backTrace(graph, result, beginWord, endWord, bPath);
            return result;
        }
    
        public static void main(String[] args) {
            Solution s = new Solution();
            String[] dict = new String[]{"hot", "dot", "dog", "lot", "log"};
            System.out.println(s.findLadders("hit", "cog", Arrays.asList(dict)));
        }
    }
    
    

Log in to reply
 

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