Share my JAVA solution, 42ms.


  • 0
    D

    The basic idea of my solution is that use two-end BFS to find the potential paths between beginWord and endWord, and use backtracking to look for the actual path.

    
    public class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
            List<List<String>> list = new LinkedList<List<String>>();
            if(wordList == null || wordList.isEmpty()) return list;
            
            Queue<Set<String>> head = new LinkedList<Set<String>>();
            Stack<Set<String>> tail = new Stack<Set<String>>();
            
            Set<String> s = new HashSet<String>();
            Set<String> e = new HashSet<String>();
            
            s.add(beginWord);
            e.add(endWord);
            
            wordList.remove(beginWord);
            wordList.remove(endWord);
            
            head.add(s);
            tail.push(e);
            
            while(!s.isEmpty() && !e.isEmpty()) {
                if(s.size() < e.size()) {
                    s = findNext(s, e, wordList);
                    if(!s.isEmpty()) head.add(s);
                } else {
                    e = findNext(e, s, wordList);
                    if(!e.isEmpty()) tail.push(e);
                }
            }
            
            
            List<Set<String>> paths = new LinkedList<Set<String>>();
            while(!head.isEmpty()) {
                paths.add(head.poll());
            }
            while(!tail.isEmpty()) {
                paths.add(tail.pop());
            }
            
            List<String> l = new LinkedList<String>();
            l.add(beginWord);
            findLadders(beginWord, paths, 1, list, l);
            return list;
        }
        
        // backtracking
        private void findLadders(String cur, List<Set<String>> paths, int index, List<List<String>> list, List<String> l) {
            if(index == paths.size()) {
                list.add(new LinkedList<String>(l));
                return ;
            }
            char[] s = cur.toCharArray();
            Set<String> next = paths.get(index);
            
            for(int i = 0; i < s.length; i++) {
                char d = s[i];
                for(char c = 'a'; c <= 'z'; c++) {
                    if(c != d) {
                        s[i] = c;
                        String ns = new String(s);
                        if(next.contains(ns)) {
                            l.add(ns);
                            findLadders(ns, paths, index + 1, list, l);
                            l.remove(l.size() - 1);
                        }
                    }
                }
                s[i] = d;
            }
        }
    
        // BFS
        private Set<String> findNext(Set<String> cur, Set<String> other, Set<String> wordList) {
            Set<String> next = new HashSet<String>();
            for(String s : cur) {
                char[] str = s.toCharArray();
                for(int i = 0; i < str.length; i++) {
                    char d = str[i];
                    for(char c = 'a'; c <= 'z'; c++) {
                        if(c != d) {
                            str[i] = c;
                            String ns = new String(str);
                            
                            if(wordList.contains(ns)) {
                                wordList.remove(ns);
                                next.add(ns);
                            } 
                            if(other.contains(ns)) return new HashSet<String>(); // merge with the other end
                        }
                    }
                    str[i] = d;
                }
            }
            return next;
        }
    }
    
    
    

Log in to reply
 

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