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


  • 59
    V
    //BFS, two-end method
    //traverse the path simultaneously from start node and end node, and merge in the middle
    //the speed will increase (logN/2)^2 times compared with one-end method
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        unordered_set<string> begSet, endSet, *set1, *set2;
        begSet.insert(start);
        endSet.insert(end);
        int h=1, K=start.size();
        while(!begSet.empty()&&!endSet.empty()){
            if(begSet.size()<=endSet.size()){   //Make the size of two sets close for optimization
                set1=&begSet;	//set1 is the forward set
                set2=&endSet;	//set2 provides the target node for set1 to search
            }
            else{
                set1=&endSet;
                set2=&begSet;
            }
            unordered_set<string> itmSet;	//intermediate Set
            h++;
            for(auto i=set1->begin();i!=set1->end();i++){
            	string cur=*i;
            	for(int k=0;k<K;k++){	//iterate the characters in string cur
            		char temp=cur[k];
            		for(int l=0;l<26;l++){	//try all 26 alphabets
            			cur[k]='a'+l;
            			auto f=set2->find(cur);
            			if(f!=set2->end())return h;
            			f=dict.find(cur);
            			if(f!=dict.end()){
            				itmSet.insert(cur);
            				dict.erase(f);
            			}
            		}
            		cur[k]=temp;
            	}
            }
            swap(*set1, itmSet);
        }
        return 0;
    }

  • 15

    Hi, VaultBoy. Thank you for your sharing. The two-end search is much faster.

    I have rewritten your code below for better readability. I hope it is Ok :)

    class Solution {
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
            wordDict.erase(beginWord);
            wordDict.erase(endWord);
            unordered_set<string> nextWords;
            unordered_set<string> prevWords;
            nextWords.insert(beginWord);
            prevWords.insert(endWord);
            int ladder = 2, len = beginWord.length();
            while (!nextWords.empty() && !prevWords.empty()) {
                if (nextWords.size() > prevWords.size())
                    swap(nextWords, prevWords);
                unordered_set<string>::iterator itr = nextWords.begin();
                unordered_set<string> temp;
                for (; itr != nextWords.end(); itr++) {
                    string word = *itr;
                    for (int p = 0; p < len; p++) {
                        char letter = word[p];
                        for (int j = 0; j < 26; j++) {
                            word[p] = 'a' + j; 
                            if (prevWords.find(word) != prevWords.end())
                                return ladder;
                            if (wordDict.find(word) != wordDict.end()) {
                                temp.insert(word);
                                wordDict.erase(word);
                            }
                        }
                        word[p] = letter;
                    }
                }
                swap(nextWords, temp);
                ladder++; 
            }
            return 0;
        }
    };

  • 10
    F

    Hi! The two pointers are unnecessary. Just use 'swap' function. This is My solution. It takes 72 ms.

    class Solution {
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
            unordered_set<string> head({beginWord}), tail({endWord});
            int minPath = 2, headLen = 1, tailLen = 1;
            while(headLen && tailLen)
            {
                if(headLen > tailLen)   //two pointers are unnecessary!
                {
                    swap(head, tail);
                    swap(headLen, tailLen);
                }
                unordered_set<string> tmpSet;
                for(auto it = head.begin(); it != head.end(); ++it)
                {
                    string str(*it);
                    for(int i = 0; i < str.size(); ++i)
                    {
                        int tmp = str[i];
                        for(char ch = 'a'; ch <= 'z'; ++ch)
                        {
                            if(ch == str[i])   continue;
                            str[i] = ch;
                            if(tail.find(str) != tail.end())
                                return minPath;
                            if(wordDict.find(str) != wordDict.end())
                            {
                                tmpSet.insert(str);
                                wordDict.erase(str);
                            }
                        }
                        str[i] = tmp;
                    }
                }
                swap(head, tmpSet);
                headLen = head.size();
                ++ minPath;
            }
            return 0;
        }
    };

  • 0

    Hi, fastcode. Thank you for your sharing. I have updated my code above. I think the use of headLen and tailLen can be replaced by the size of the corresponding set.


  • 0
    F

    Why will the speed increase (logN/2)^2 times compared with one-end method ?
    I think it is just around 2x as fast, depending on the degree of each node in this graph tho


  • 0
    R

    it is amazing code, thanks a lot


  • 0
    V

    Sorry for the late response. I made a mistake here. The speed increases not only (logN/2)^2. It increases (logN/2)^m, where m is the average number of neighbors per node. just imagine the graph as a m-tree, then you will find out why.


  • 0
    F

    Actually I think it is sqrt(N)/2 times faster. I don't see why it is (logN/2)^m;


  • 22
    S

    Two-end BFS is much faster! Share my rewritten java version solution.

    public class Solution {
    
        public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
            int len = 1;
            Set<String> beginSet = new HashSet<>();
            Set<String> endSet = new HashSet<>();
            Set<String> visited = new HashSet<>();
            beginSet.add(beginWord);
            endSet.add(endWord);
            visited.add(beginWord);
            visited.add(endWord);
            
            while (!beginSet.isEmpty() && !endSet.isEmpty()) {
                // add new words to smaller set to achieve better performance
                boolean isBeginSetSmall = beginSet.size() < endSet.size();
                Set<String> small = isBeginSetSmall ? beginSet : endSet;
                Set<String> big = isBeginSetSmall ? endSet : beginSet;
                Set<String> next = new HashSet<>();
                len++;
                for (String str : small) {
                    // construct all possible words
                    for (int i = 0; i < str.length(); i++) {
                        for (char ch = 'a'; ch <= 'z'; ch++) {
                            StringBuilder sb = new StringBuilder(str);
                            sb.setCharAt(i, ch);
                            String word = sb.toString();
                            if (big.contains(word)) {
                                return len;
                            }
                            if (wordDict.contains(word) && !visited.contains(word)) {
                                visited.add(word);
                                next.add(word);
                            }
                        }
                    }
                }
                if (isBeginSetSmall) {
                    beginSet = next;
                } else {
                    endSet = next;
                }
            }
            return 0;
        }
    
    }

  • 0

    I think this is by far the best answer! Thanks for sharing. Only 39ms.


  • 3
    C

    I agree with sqrt(N)/2. Say the ladder is of length 'len', and each word branches out 'm' new words.

    From one end, we have to generate O(m^len) branches. Yet from both ends, we are only supposed to generate O(2m^(len/2)) braches. So we are sqrt(m^len)/2 times faster. Correct me if I'm wrong.


  • 0
    S

    What happens if the two input strings are the same? This algo will return 2 but I think the correct solution is 1.


  • 0
    L

    We can keep track of the original char at position i by 'char ori = sb.charAt(i);' and put back the char at the end of each iteration by 'sb.setCharAt(i,ori);'. This leads to 26ms run time.


  • 0
    A

    Did some improvements.

    public int LadderLength(string beginWord, string endWord, ISet<string> wordList) {
            if (beginWord==endWord) { return 1; }
            HashSet<string> beginSet = new HashSet<string>();
            HashSet<string> endSet = new HashSet<string>();
            HashSet<string> visited = new HashSet<string>();
            int len = 1;
            beginSet.Add(beginWord);
            endSet.Add(endWord);
            visited.Add(beginWord);
            visited.Add(endWord);
            while (beginSet.Count!=0 && endSet.Count!=0){
                if (beginSet.Count>endSet.Count){
                    // swap reference
                    HashSet<string> temp = beginSet;
                    beginSet = endSet;
                    endSet = temp;
                }
                len++;
                HashSet<string> next = new HashSet<string>();
                foreach(string word in beginSet){
                    StringBuilder newWord = new StringBuilder(word);
                    for (int i=0; i<word.Length; i++){  // test each position
                        char pre = newWord[i];
                        for (char ch='a'; ch<='z'; ch++){  // test a-z
                            newWord[i] = ch;
                            string str = newWord.ToString();
                            if (endSet.Contains(str)){
                                return len;
                            }
                            if (wordList.Contains(str) && !visited.Contains(str)){
                                next.Add(str);
                                visited.Add(str);
                            }
                        }
                        newWord[i] = pre;   // revert change
                    }
                }
                beginSet = next;
            }
            return 0;
        }

  • 0
    N
    This post is deleted!

  • 0
    P

    @cqnkxy
    Sorry, I don't get it.

    Assume the size of set is N. If we consider the worse case: the two sets meet as we visit the very last string. Given that two sets are balanced, each set contains N/2 strings in the worst case. If each word branches out M new words, the height of the 'tree' in 'two-end BFS' should be O(log(N/2)/log(M)), compared to O(log(N)/log(M)) in 'one-end BFS'.

    The fact is, the number of branches generated by words decays as the search becomes deeper, because some branches are already visited.


Log in to reply
 

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