two-end BFS runs 33ms with explanation


  • 1
    W

    one end BFS runs more than 200 ms, it's very slow. Why slow? suppose there have x step to reach the end word from the start word, there would be 26 * 26 * 26 ......* 26 == 26^step.This number is very huge, finally it just find one word in this number of string. It looks like a triangle, the end word in the the last column.

    
                               a
                               b
                               c
                 a            .
                 b            .
    s           c             e
                 .             y
                 .             .
                 z            .
                              z
    

    However, if it goes from start word and end word, let's meet in the middle, the triangle would be shaped like a diamond( 菱形 ), the max length of column would be much shorter than the triangle. The formula is
    26^step is much more bigger than 26^(step/2) + 26^(step/2). For example,
    step == 6, 26^6 == 308915776 compare to 26^3+26^3 == 35152. It significantly improved the running time performance. Here is my code.

        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            if(!wordList.contains(endWord)) return 0;
            Set<String> beginSet = new HashSet<>();
            Set<String> endSet = new HashSet<>();
            Set<String> dic = new HashSet<>(wordList);
            beginSet.add(beginWord);
            endSet.add(endWord);
            int step = 1;
            Set<String> visited = new HashSet<>();
            while(!beginSet.isEmpty() &&!endSet.isEmpty()) {
                if(beginSet.size() > endSet.size()) {
                    Set<String> tmp = beginSet;
                    beginSet = endSet;
                    endSet = tmp;
                }
                
                Set<String> tmp = new HashSet<>();
                for(String str : beginSet) {
                    for(int i = 0; i < str.length(); i++) {
                        char[] chars = str.toCharArray();    
                        for(char a = 'a'; a <= 'z'; a++) {
                            chars[i] = a;
                            String newV = String.valueOf(chars);
                            if(endSet.contains(newV)) return step+1;
                            if(dic.contains(newV) && visited.add(newV)) {
                                dic.remove(newV);
                                tmp.add(newV);
                            }
                        }
                    }
                }
                step++;
                beginSet = tmp;
            }
            return 0;
        }

  • 0
    S

    great explanation!


Log in to reply
 

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