Two end BFS java solution, 26ms beat 99.62%

  • 0
        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<>();
            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)) {
                    chArr[i] = c;
            return twoEndBFS(temp, q2, dic, len + 1);

  • 0

    Why do you store the wordList from an ArrayList to a Set in dic?

    Why can't you use the ArrayList wordList itself when removing and comparing elements?

  • 0

    @deepak_um The reason is that HashSet.contains() has O(1) time complexity, while checking in ArrayList costs O(n), where n is the length of the ArrayList.

Log in to reply

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