Two end BFS java solution, 26ms beat 99.62%


  • 0
    M
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            if (wordList == null || wordList.size() == 0) return 0;
            Set<String> dic = new HashSet<>(wordList);
            if (!dic.contains(endWord)) return 0;
            if (beginWord.equals(endWord)) return 1;
            Set<String> q1 = new HashSet<>(), q2 = new HashSet<>();
            q1.add(beginWord);
            dic.remove(beginWord);
            q2.add(endWord);
            dic.remove(endWord);
            return twoEndBFS(q1, q2, dic, 2);
        }
    
        private int twoEndBFS(Set<String> q1, Set<String> q2, Set<String> dic, int len) {
            if (q1.isEmpty() || q2.isEmpty()) return 0;
            if (q1.size() > q2.size()) return twoEndBFS(q2, q1, dic, len);
    
            Set<String> temp = new HashSet<>();
            for (String word : q1) {
                char[] chArr = word.toCharArray();
                for (int i = 0; i < chArr.length; ++i) {
                    char c = chArr[i];
                    for (char newC = 'a'; newC <= 'z'; ++newC) {
                        chArr[i] = newC;
                        String next = new String(chArr);
                        if (q2.contains(next)) return len;
                        if (dic.contains(next)) {
                            temp.add(next);
                            dic.remove(next);
                        }
                    }
                    chArr[i] = c;
                }
            }
            return twoEndBFS(temp, q2, dic, len + 1);
        }
    

Log in to reply
 

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