Sharing my code....108ms JAVA solution


  • 0
    D

    Maybe too long but works.... only one time bidirectional BFS. It remembers the paths when searching, and combine the paths when a connection is found.

    public class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
            List<List<String>> result = new ArrayList<List<String>>();
            
            //initial check
            if (beginWord==endWord) {
                List<String> singlePath = new ArrayList<String>();
                singlePath.add(beginWord);
                singlePath.add(endWord);
                result.add(singlePath);
                return result;
            }
            if (wordList.isEmpty()) return result;
            
            int capacity = (wordList.size()*4/3)+1;
            //init map (from start)
            HashMap<String, Node> fromStart = new HashMap<String, Node>(capacity);
            Node beginNode = new Node(0, true);
            beginNode.paths.add(beginWord); 
            fromStart.put(beginWord, beginNode);
            //init map (from end)
            HashMap<String, Node> fromEnd = new HashMap<String, Node>(capacity);
            Node endNode = new Node(0, false);
            endNode.paths.add(endWord); 
            fromEnd.put(endWord, endNode);
            //init queue (from start)
            Queue<String> queueStart = new LinkedList<String>();
            queueStart.offer(beginWord);
            //init queue (from end)
            Queue<String> queueEnd = new LinkedList<String>();
            queueEnd.offer(endWord);
            
            //breath first search (and fill the result)
            bfs(result, fromStart, fromEnd, queueStart, queueEnd, wordList);
            
            return result;
        }
        
        private void bfs(
            List<List<String>> result, 
            Map<String, Node> m1, Map<String, Node> m2, 
            Queue<String> q1, Queue<String> q2, 
            Set<String> wordList
        ) {
            boolean pathFound = false;  
            int size = q1.size();
            while (size-->0) {
                String word = q1.poll();
                Node node = m1.remove(word);
                
                char[] chars = word.toCharArray();
                for (int i = 0; i < chars.length; ++i){
                    char symb = chars[i];
                    for (char c = 'a'; c <= 'z'; ++c){
                        chars[i] = c;
                        String tmpWord = String.valueOf(chars);
                        Node next = null;
                        if (m2.containsKey(tmpWord)){
                            pathFound = true;
                            addSolutions(result, node, m2.get(tmpWord));
                            continue;
                        } else if (m1.containsKey(tmpWord)) {
                            Node another = m1.get(tmpWord);
                            if (another.step==node.step+1) next = another;
                        } else if (wordList.remove(tmpWord)){
                            next = new Node(node.step+1, node.isFromStart);
                            m1.put(tmpWord, next);
                            q1.offer(tmpWord);
                        }
                        if (next != null) for (String path: node.paths) next.paths.add(path+","+tmpWord);
                    }
                    chars[i] = symb;
                }
            }
            
            if (pathFound || q1.isEmpty()) return;
            bfs(result, m2, m1, q2, q1, wordList);
        }
        
        private class Node{
            public int step;
            public List<String> paths;
            boolean isFromStart;
            
            public Node(int step, boolean isFromStart) {
                this.step = step;
                this.isFromStart = isFromStart;
                this.paths = new ArrayList<String>();
            }
        }
        
        private void addSolutions(List<List<String>> result, Node n1, Node n2) {
            Node fromStart, fromEnd;
            if (n1.isFromStart) {
                fromStart = n1;
                fromEnd = n2;
            } else {
                fromStart = n2;
                fromEnd = n1;
            }
            for (String a: fromStart.paths) {
                for (String b: fromEnd.paths) {
                    String[] x = a.split(",");
                    String[] y = b.split(",");
                    List<String> solution = new ArrayList<String>();
                    for (int i=0;i<x.length;i++) solution.add(x[i]);
                    for (int j=y.length-1; j>=0;j--) solution.add(y[j]);
                    result.add(solution);
                }
            }
        }
    }
    

Log in to reply
 

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