Share my Clean BFS AC Java solution.


  • 0
    T

    Use BFS. Every time, only keep list of words that goes further.
    Used a temp HashSet "visited" to keep visited Strings of each level, so that each word can be visited more than once per level, but not afterwords

        public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
            List<List<String>> res = new LinkedList<>();
            List<LinkedList<String>> cur = new LinkedList<>();
            List<LinkedList<String>> next = new LinkedList<>();
            if (wordList.contains(beginWord)) {
                wordList.remove(beginWord);
            }
            LinkedList<String> initList = new LinkedList<>();
            initList.add(beginWord);
            cur.add(initList);
            while (!cur.isEmpty() && res.size() == 0) {
                Set<String> visited = new HashSet<>();
                for (LinkedList<String> list : cur) {
                    StringBuilder sb = new StringBuilder(list.getLast());
                    for (int i = 0; i < sb.length(); i++) {
                        char holder = sb.charAt(i);
                        for (char c = 'a'; c <= 'z'; c++) {
                            if (c == holder) {
                                continue;
                            }
                            sb.setCharAt(i, c);
                            String word = sb.toString();
                            if (word.equals(endWord)) {
                                List<String> resList = new LinkedList<>(list);
                                resList.add(endWord);
                                res.add(resList);
                            } else if (wordList.contains(word) || visited.contains(word)) {
                                wordList.remove(word);
                                visited.add(word);
                                LinkedList<String> nextList = new LinkedList<String>(list);
                                nextList.add(word);
                                next.add(nextList);
                            }
                        }
                        sb.setCharAt(i, holder);
                    }
                }
                cur = next;
                next = new LinkedList<>();
            }
            return res;
        }
    

Log in to reply
 

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