Two-end BFS in Java 31ms.


  • 100
    M

    Modified from Share my two-end BFS in C++ 80ms.

    public class Solution {
    
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
    	Set<String> beginSet = new HashSet<String>(), endSet = new HashSet<String>();
    
    	int len = 1;
    	int strLen = beginWord.length();
    	HashSet<String> visited = new HashSet<String>();
    	
    	beginSet.add(beginWord);
    	endSet.add(endWord);
    	while (!beginSet.isEmpty() && !endSet.isEmpty()) {
    		if (beginSet.size() > endSet.size()) {
    			Set<String> set = beginSet;
    			beginSet = endSet;
    			endSet = set;
    		}
    
    		Set<String> temp = new HashSet<String>();
    		for (String word : beginSet) {
    			char[] chs = word.toCharArray();
    
    			for (int i = 0; i < chs.length; i++) {
    				for (char c = 'a'; c <= 'z'; c++) {
    					char old = chs[i];
    					chs[i] = c;
    					String target = String.valueOf(chs);
    
    					if (endSet.contains(target)) {
    						return len + 1;
    					}
    
    					if (!visited.contains(target) && wordList.contains(target)) {
    						temp.add(target);
    						visited.add(target);
    					}
    					chs[i] = old;
    				}
    			}
    		}
    
    		beginSet = temp;
    		len++;
    	}
    	
    	return 0;
    }
    }
    

  • 7
    W

    Can someone help me understand why two-way BFS speeds up BFS? It is still O(n) because you need to traverse all the nodes in between, right?


  • 2
    M

    Convert this problem to a math problem: Find a shortest path from one Vertex to another in a graph.
    Then searching from both Vertexes always visits less Vertexes than searching from one Vertex.
    But I can't prove this theory. :(
    Maybe it is already proved.


  • 0
    Y

    great solution! simply loving it, esp. using two ends by alternating beginSet and endSet


  • 20
    Y

    hi @watera427, i think the intuition is that you are replacing a big search tree in the one-end solution with two smaller trees in the two-end solution. Both solutions have the same TOTAL depth, yet tree width grows exponentially w.r.t. depths, and the two-end solutions results in less nodes being visited.


  • 0
    W

    It starts to make sense. Thanks a lot for all the explanations!


  • 1
    D

    Though simply remove target from wordList will be more efficient, but will modify original parameters.
    So I suggest using this HashSet to keep all visited is more suitable.
    Nice job!


  • 74
    K

    "The idea behind bidirectional search is to run two simultaneous searches—one forward from
    the initial state and the other backward from the goal—hoping that the two searches meet in
    the middle. The motivation is that b^(d/2) + b^(d/2) is much less than b^d. b is branch factor, d is depth. "

    ----- section 3.4.6 in Artificial Intelligence - A modern approach by Stuart Russel and Peter Norvig


  • 3

    These two lines can be put out of "for (char c = 'a'; c <= 'z'; c++)" Loop


    char old = chs[i];
    ............
    chs[i] = old;



  • 2
    N

    How to analyze the time complexity?


  • 3
    L

    Thanks bro, just finish the python version

    class Solution(object):
        def ladderLength(self, beginWord, endWord, wordList):
            """
            :type beginWord: str
            :type endWord: str
            :type wordList: Set[str]
            :rtype: int
            """
            
            beginSet = set()
            endSet = set()
            beginSet.add(beginWord)
            endSet.add(endWord)
            
            
            result = 2
            while len(beginSet) != 0 and len(endSet) != 0:
                if len(beginSet) > len(endSet):
                    beginSet, endSet = endSet, beginSet
                nextBeginSet = set()
                for word in beginSet:
                    for ladderWord in self.wordRange(word):
                        if ladderWord in endSet:
                            return result
                        if ladderWord in wordList:
                            nextBeginSet.add(ladderWord)
                            wordList.remove(ladderWord)
                beginSet = nextBeginSet
                result += 1
                print(beginSet)
                print(result)
            return 0
                            
        
        
        def wordRange(self, word):
            for ind in xrange(len(word)):
                tempC = word[ind]
                for c in [chr(x) for x in xrange(ord('a'), ord('z')+1)]:
                    if c != tempC:
                        yield word[:ind] + c + word[ind+1:]
    

  • 12
    Q

    @kleklokin I don't think that's the case, since the time complexicity is 26 * O(n), not exponential, n is the length of wordList(only the word in the dict will do a 26-loop, and each word only do it once). The reason that this approach is fast because after each bfs, it always choose the set that has the smaller size, which means it always try to waste less computation to meet the goal(the set that has the maximum size won't need to generate new words). if you delete the code "if (beginSet.size() > endSet.size()) ", just simply swtich the role of begin and end each time, it will take 80+ms again.


  • 0

    @qiyidk I agree with you. I think the reason is bidirectional will save the last search with 16 * maxSetNum * wordLength instead of search all nodes, where maxSetNum means the breadth with maximum nodes in BFS. Slightly modified your answer :)


  • 0
    K

    @qiyidk Yes, you're correct


  • 0
    J

    @Izana @qiyidk I agree with you with the same idea! But now I am still struggling with the very detail.

    I mean,
    when N is dictionary.length and L is word.length;
    the time complexity for 1 directional BFS is N * 26 * L
    the time complexity for 1 directional BFS is N / 2 * 26 * L

    Am I right?


  • 30

    At last I'm able to understand. I learned a lot from this solution.

    1. It's much faster than one-end search indeed as explained in wiki.
    2. BFS isn't equivalent to Queue. Sometimes Set is more accurate representation for nodes of level. (also handy since we need to check if we meet from two ends)
    3. It's safe to share a visited set for both ends since if they meet same string it terminates early. (vis is useful since we cannot remove word from dict due to bidirectional search)
    4. It seems like if(set.add()) is a little slower than if(!contains()) then add() but it's more concise.

    Thank you all for sharing and explaining!

    update: the dictList is of List type now. And all transformed words including endWord must be in dictList.

        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            Set<String> dict = new HashSet<>(wordList), qs = new HashSet<>(), qe = new HashSet<>(), vis = new HashSet<>();
            qs.add(beginWord);
            if (dict.contains(endWord)) qe.add(endWord); // all transformed words must be in dict (including endWord)
            for (int len = 2; !qs.isEmpty(); len++) {
                Set<String> nq = new HashSet<>();
                for (String w : qs) {
                    for (int j = 0; j < w.length(); j++) {
                        char[] ch = w.toCharArray();
                        for (char c = 'a'; c <= 'z'; c++) {
                            if (c == w.charAt(j)) continue; // beginWord and endWord not the same, so bypass itself
                            ch[j] = c;
                            String nb = String.valueOf(ch);
                            if (qe.contains(nb)) return len; // meet from two ends
                            if (dict.contains(nb) && vis.add(nb)) nq.add(nb); // not meet yet, vis is safe to use
                        }
                    }
                }
                qs = (nq.size() < qe.size()) ? nq : qe; // switch to small one to traverse from other end
                qe = (qs == nq) ? qe : nq;
            }
            return 0;
        }
    

  • 5
    C

    Thanks to you share.
    This is my code with some small modifications. Run time is 23ms.

    public class Solution {

    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        int pathLength = 2;
        
        Set<String> start = new HashSet<>();
        Set<String> end = new HashSet<>();
        start.add(beginWord);
        end.add(endWord);
        wordList.remove(beginWord);
        wordList.remove(endWord);
        
        while(!start.isEmpty()){
            if(start.size() > end.size()){
                Set<String> temp = start;
                start = end;
                end = temp;
            }
            Set<String> next = new HashSet<>();
            for(String cur : start){
                char[] strArray = cur.toCharArray();
                for(int i = 0; i < strArray.length;i++){
                    char old = strArray[i];
                    for(char c = 'a';c <= 'z';c++){
                        strArray[i] = c;
                        String str = String.valueOf(strArray);
                        if(end.contains(str)){
                            return pathLength;
                        }
                        if(wordList.contains(str)){
                            next.add(str);
                            wordList.remove(str);
                        }
                    }
                    strArray[i] = old;
                }
            }
            start = next;
            pathLength++;
        }
        return 0;
        
    }
    

    }


  • 0
    S

    @Moriarty your code is pretty good. can we use the same for solving word ladder II problem https://leetcode.com/problems/word-ladder-ii/ we need to return all the shortest ladders


  • 0
    I

    Nice solution. I think if we remove the visited matrix, it will still work.


  • 1
    K

    Thanks to your share.
    This is the javascript version.

    const ladderLength = function (beginWord, endWord, wordList) {
        let beginSet = new Set(),
            endSet   = new Set(),
            visited  = new Set();
    
        let len = 1;
        let strLen = beginWord.length;
    
        beginSet.add(beginWord);
        endSet.add(endWord);
    
        while (beginSet.size && endSet.size) {
            if (beginSet.size > endSet.size) {
                let set = beginSet;
                beginSet = endSet;
                endSet = set;
            }
    
            let temp = new Set();
    
            for (var word of beginSet) {
                let chs = word.split('');
    
                for (var i = 0, l = chs.length; i < l; ++i) {
                    for (let c = 97; c <= 122; ++c) {
                        let old = chs[i];
                        chs[i] = String.fromCharCode(c);
                        let target = chs.join('');
    
                        if (endSet.has(target)) {
                            return len + 1;
                        }
    
                        if (!visited.has(target) && wordList.has(target)) {
                            temp.add(target);
                            visited.add(target);
                        }
    
                        chs[i] = old;
                    }
                }
            }
    
            beginSet = temp;
            ++len;
        }
    
        return 0;
    }
    

Log in to reply
 

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