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


  • 61
    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;
    }

  • 17

    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;
        }
    };

  • 11
    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;


  • 24
    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.


  • 0
    G

    I am a little confused about using just BFS. BFS gives "a Path" and not necessarily the shortest path.


  • 0
    G

    @gkotecha
    I did a little bit reading and realized BFS will give the shortest path if the all the edges are of same distance which is true here(as all edges are "1"). I think probably that is the reason it works.


Log in to reply
 

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