JAVA concise DFS + BFS beats 90%


  • -1
    R
    public class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
            List<List<String>> res = new ArrayList<>();
            List<Set<String>> wordStep = bfsStep(beginWord, endWord, wordList);
            Set<String> begin = wordStep.get(wordStep.size() - 1);
            if(begin.size() == 0) return res;
            List<String> item = new ArrayList<>();
            item.add(beginWord);
            dfs(beginWord, endWord, wordStep, res, item, wordStep.size() - 2);
            return res;
        }
        
        private void dfs(String beginWord, String endWord, List<Set<String>> wordStep, 
                    List<List<String>> res, List<String> item, int index) {
            if(index == -1) {
                res.add(new ArrayList<>(item));
                return;
            }
            
            for(String cur : wordStep.get(index)) {
                if(isNext(beginWord, cur)) {
                    item.add(cur);
                    dfs(cur, endWord, wordStep, res, item, index - 1);
                    item.remove(item.size() - 1);
                }
            }
        }
        
        
        
        private boolean isNext(String pre, String next) {
            int count = 0;
            for(int i = 0; i < pre.length(); i++) {
                if(pre.charAt(i) != next.charAt(i)) count++;
                if(count > 1) return false;
            }
            return count == 1;
        }
        
        
        
        private List<Set<String>> bfsStep(String beginWord, String endWord, Set<String> wordList) {
            List<Set<String>> wordStep = new ArrayList<>();
            wordList.add(beginWord);
            Set<String> set = new HashSet<>();
            set.add(endWord);
            wordStep.add(set);
            int start = 0;
            while(!wordList.isEmpty()) {
                set = wordStep.get(start++);
                Set<String> newSet = new HashSet<>();
                for(String w : set) {
                    char[] chs = w.toCharArray();
                    for(int i = 0; i < chs.length; i++) {
                        char tmp = chs[i];
                        for(char ch = 'a'; ch <= 'z'; ch++) {
                            if(ch == tmp) continue;
                            chs[i] = ch;
                            String key = new String(chs);
                            if(wordList.contains(key)) {
                                newSet.add(key);
                                wordList.remove(key);
                            }
                        }
                        chs[i] = tmp;
                    }
                }
                wordStep.add(newSet);
                if(newSet.contains(beginWord) || newSet.size() == 0) break;
            }
            return wordStep;
        }
    }

Log in to reply
 

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