Java solution: hash, BFS, DFS


  • 0
    L
    class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            ArrayList<Long> exp = new ArrayList<>();
            long pow = 1;
            for (int i = 0; i < beginWord.length(); i++) {
                exp.add(pow);
                pow *= 27;
            }
            HashMap<Long, ArrayList<String>> map = new HashMap<>();
            HashMap<String, List<Long>> hashvalues = new HashMap<>();
            wordList.add(beginWord);
            for (String s: wordList) {
                List<Long> values = hashes(s, exp);
                hashvalues.put(s, values);
                for (Long key:values) {
                    if (map.containsKey(key)) {
                        map.get(key).add(s);
                    } else {
                        ArrayList<String> new_list = new ArrayList<>();
                        new_list.add(s);
                        map.put(key, new_list);
                    }
                }
            }
            HashSet<String> set = new HashSet<>();
            set.add(beginWord);
            Queue<String> queue = new LinkedList<>();
            queue.add(beginWord);
            
            HashMap<String, DAG> graph = new HashMap<>();
            
            int step = 0;
            boolean end = false;
            HashSet<String> current = new HashSet<>();
            while (!end && !queue.isEmpty()) {
                current.clear();
                step++;
                end = false;
                int len = queue.size();
                for (int i = 0; i < len; i++) {
                    String temp = queue.poll();
                    if (temp.equals(endWord)) {
                        end = true;
                    } else {
                        for (long key: hashvalues.get(temp)) { 
                            for (String s:map.get(key)) {
                                // neighbors
                                if (!set.contains(s) && !s.equals(temp)) {
                                    current.add(s);
                                    if (graph.containsKey(s)) {
                                        graph.get(s).nb.add(temp);
                                    } else {
                                        DAG node = new DAG(s);
                                        node.nb.add(temp);
                                        graph.put(s,node);
                                    }
                                    queue.offer(s);
                                    set.add(s);
                                } else if (current.contains(s) && !s.equals(temp)) {
                                    graph.get(s).nb.add(temp);
                                }
                            }
                        } 
                    }
                }
            }
            List<List<String>> ans = new ArrayList<>();
            if (!graph.containsKey(endWord)) {
                return ans;
            }
            return dfs(graph, endWord, new ArrayList<>());
         
        }
        
        List<Long> hashes(String s, ArrayList<Long> exp) {
            ArrayList<Long> list = new ArrayList<>();
            
            for (int i = 0; i < s.length(); i++) {
                list.add((s.charAt(i) - 96) * exp.get(i));
            }
            ArrayList<Long> hash = new ArrayList<>();
            for (int i = 0; i < s.length(); i++) {
                long temp = 0;
                for (int j = 0; j < s.length(); j++) {
                    if (i != j) {
                        temp += list.get(j);
                    }
                }
                hash.add(temp);
            }
            return hash;
        }
        
        List<List<String>> dfs(HashMap<String, DAG> graph, String s, List<String> path) {
            List<List<String>> ans = new ArrayList<>();
            path.add(0, s);
            if (!graph.containsKey(s)) {
                ans.add(path);
                return ans;
            }
            for (String next:graph.get(s).nb) {
                ans.addAll(dfs(graph, next, new ArrayList<>(path)));
            }
            return ans;
        }
    }
    
    class DAG {
        String val;
        ArrayList<String> nb;
        public DAG(String s) {
            this.val = s;
            nb = new ArrayList<>();
        }
    }
    

Log in to reply
 

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