Easy 76ms C++ Solution using BFS


  • 100

    Well, this problem has a nice BFS structure.

    Let's see the example in the problem statement.

    start = "hit"

    end = "cog"

    dict = ["hot", "dot", "dog", "lot", "log"]

    Since only one letter can be changed at a time, if we start from "hit", we can only change to those words which have only one different letter from it, like "hot". Putting in graph-theoretic terms, we can say that "hot" is a neighbor of "hit".

    The idea is simpy to begin from start, then visit its neighbors, then the non-visited neighbors of its neighbors... Well, this is just the typical BFS structure.

    To simplify the problem, we insert end into dict. Once we meet end during the BFS, we know we have found the answer. We maintain a variable dist for the current distance of the transformation and update it by dist++ after we finish a round of BFS search (note that it should fit the definition of the distance in the problem statement). Also, to avoid visiting a word for more than once, we erase it from dict once it is visited.

    The code is as follows.

    class Solution {
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
            wordDict.insert(endWord);
            queue<string> toVisit;
            addNextWords(beginWord, wordDict, toVisit);
            int dist = 2;
            while (!toVisit.empty()) {
                int num = toVisit.size();
                for (int i = 0; i < num; i++) {
                    string word = toVisit.front();
                    toVisit.pop();
                    if (word == endWord) return dist;
                    addNextWords(word, wordDict, toVisit);
                }
                dist++;
            }
        }
    private:
        void addNextWords(string word, unordered_set<string>& wordDict, queue<string>& toVisit) {
            wordDict.erase(word);
            for (int p = 0; p < (int)word.length(); p++) {
                char letter = word[p];
                for (int k = 0; k < 26; k++) { 
                    word[p] = 'a' + k;
                    if (wordDict.find(word) != wordDict.end()) {
                        toVisit.push(word);
                        wordDict.erase(word);
                    }
                }
                word[p] = letter;
            } 
        } 
    };
    

    The above code can still be speeded up if we also begin from end. Once we meet the same word from start and end, we know we are done. This link provides a nice two-end search solution. I rewrite the code below for better readability. Note that the use of two pointers phead and ptail save a lot of time. At each round of BFS, depending on the relative size of head and tail, we point phead to the smaller set to reduce the running time.

    class Solution {
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
            unordered_set<string> head, tail, *phead, *ptail;
            head.insert(beginWord);
            tail.insert(endWord);
            int dist = 2;
            while (!head.empty() && !tail.empty()) {
                if (head.size() < tail.size()) {
                    phead = &head;
                    ptail = &tail;
                }
                else {
                    phead = &tail; 
                    ptail = &head;
                }
                unordered_set<string> temp; 
                for (auto itr = phead -> begin(); itr != phead -> end(); itr++) {
                    string word = *itr;
                    wordDict.erase(word);
                    for (int p = 0; p < (int)word.length(); p++) {
                        char letter = word[p];
                        for (int k = 0; k < 26; k++) {
                            word[p] = 'a' + k;
                            if (ptail -> find(word) != ptail -> end())
                                return dist;
                            if (wordDict.find(word) != wordDict.end()) {
                                temp.insert(word);
                                wordDict.erase(word);
                            }
                        }
                        word[p] = letter;
                    }
                }
                dist++;
                swap(*phead, temp);
            }
            return 0; 
        }
    };
    

  • 0

  • 0
    A
    This post is deleted!

  • 2
    A

    First of all, thanks for your detail comment.
    But in your first solution, I think, "wordDict.erase(word);" can be deleted(the first statement in function addNextWords), because it is not necesary since you have deleted the word when it is pushed in the queue, so it just influence the beginWord, we delete the beginWord if it exist in toVisit.


  • 0
    J

    Firstly, thank you for the detailed explanation. It is very helpful! I have a question here, since the problems requests "shortest transformation sequence ", I see you return "dist" when finding the endword. How can you make sure dist is the smallest? Thank you!


  • 0

    Well, since adjacent words can only have one different letter and we search for the next words while sticking to this requirement using BFS, the dist will be the answer when the endWord is hit.


  • 0
    I

    I think so and so as in the two-end search solution.


  • 2
    N

    What would be the time and space complexity ?


  • 0
    R

    I did not understand why you pushed
    wordDict.insert(endWord);
    in the beginning. How is it making the solution easy? As even without it it is working


  • -3
    O

    Share my java Solution, 26ms, use a HashMap to mark whether a word is not yet visited or it is visited by head / tail queue.

    public class Solution {
        public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
            
            HashMap<String, Integer> h = new HashMap();
            for (String i : wordList) h.put(i, 0);
            ArrayList<String> l = new ArrayList(), r = new ArrayList();
            l.add(beginWord); r.add(endWord);
            h.put(beginWord, 1); h.put(endWord, -1);
            
            int i = 0, j = 0;
            while (i < l.size() && j < r.size()) {
                int curStep = h.get(l.get(i));
                char[] c = l.get(i).toCharArray();
                for (int t = 0; t < c.length; t++) {
                    char cc = c[t];
                    for (char x = 'a'; x <= 'z'; x++) if (x != cc) {
                        c[t] = x;
                        String y = String.valueOf(c);
                        if (h.containsKey(y)) {
                            int step = h.get(y);
                            if (step == 0) {
                                l.add(y);
                                h.put(y, curStep + 1);
                            } 
                            else
                            if (step < 0) {
                                return curStep - step;
                            }
                        }
                        c[t] = cc;
                    }
                }
                i++;
                
                
                curStep = h.get(r.get(j));
                c = r.get(j).toCharArray();
                for (int t = 0; t < c.length; t++) {
                    char cc = c[t];
                    for (char x = 'a'; x <= 'z'; x++) if (x != cc) {
                        c[t] = x;
                        String y = String.valueOf(c);
                        if (h.containsKey(y)) {
                            int step = h.get(y);
                            if (step == 0) {
                                r.add(y);
                                h.put(y, curStep - 1);
                            } 
                            else
                            if (step > 0) {
                                return step - curStep;
                            }
                        }
                        c[t] = cc;
                    }
                }
                j++;
            }
            return 0;
        }
    }

  • 1
    O

    Thank you for sharing this awesome code!
    It's straightforward and easy to understand and well explained.

    The following is my take based on your code, added some comments and used more explicit variable names.
    Hope it could help somebody.

        class Solution {
        
        public:
            
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
                
        /*
                
        Search from both ends.
                
        From 'beginWord', find the set of words which are one character from 'beginWord'.
                
        Do the same to 'endWord', form a set of words one character from 'endWord'.
        
        Check each word in the smaller of 'beginWord'/'endWord', if it is in the other set.
        If it is, we are done.
        Otherwise, for each word in 'begigWord'/'endWord', update the set (by changing one character)
        */
        
        unordered_set<string> head, tail, *smallerSet, *biggerSet;
        head.insert(beginWord);
        tail.insert(endWord);
        
        int dist = 1;
        while (!head.empty() && !tail.empty()) {
            ++dist;
            
            smallerSet = (head.size() < tail.size()) ? &head : &tail;
            biggerSet = (head.size() < tail.size()) ? &tail : &head;
    
            unordered_set<string> reachableWords; 
            //for (auto itr = smallerSet->begin(); itr != smallerSet->end(); ++itr)
            for(const auto& w: *smallerSet)
            {
                string word(w);
                wordDict.erase(word);
                
                for (int i = 0; i < (int)word.length(); ++i) 
                {
                    char letter = word[i];
                    for (int c = 0; c < 26; ++c)
                    {
                        word[i] = 'a' + c;
                        if (biggerSet->find(word) != biggerSet->end())
                            return dist;
                        if (wordDict.find(word) != wordDict.end()) 
                        {
                            reachableWords.insert(word);
                            wordDict.erase(word);
                        }
                    }
                    word[i] = letter;
                }
            }
            swap(*smallerSet, reachableWords);
        }
        return 0; 
    }
        };

  • 0
    P

    how clever you are! so beautiful!


  • 1
    S

    It indeed costs 280ms.

    New test cases might've been added since post


  • 0
    N

    Seems having problem for the second solution. If the endWord is one character different from the beginWord, and the beginWord is not in the dictionary, it will return 2, but actually the length could either be zero or larger than 2.


  • 1
    N

    @nosrepus That is because in the end you need to return 0, not dist.
    dist is always returned when the last word is found, in the loop.


  • 0
    H
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
    	int res = 1;
    	deque<string> candidate;
    	deque<string> cur;
    	cur.push_back(beginWord);
    	wordList.erase(beginWord);
    	string temp;
    	while (!cur.empty()) {
    		while (!cur.empty()) {
    			beginWord = cur.front();
    			cur.pop_front();
    			for (int i = 0;i<endWord.size();i++) {
    				temp = beginWord;
    				for (int j = 0;j<26;j++) {
    					temp[i] = 'a' + j;
    					if (temp == endWord) return res+1;
    					if (temp != beginWord&&wordList.find(temp) != wordList.end()) {
    						candidate.push_front(temp);
    						wordList.erase(temp);
    					}
    				}
    			}
    		}
    		swap(cur, candidate);
    		res++;
    	}
    	return 0;
    }
    

  • 5

    Thanks for sharing! Here's my similar Java version. I use visited set explicitly rather than modify dict which is more straightforward in my view.

    update (2017/03/01): wordList is of List type now. And all transformed words (including endWord) must be in dictionary.
    For more efficiency, please refer to my bidirectional BFS solution (https://discuss.leetcode.com/topic/29303/two-end-bfs-in-java-31ms/16).

        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            Set<String> dict = new HashSet<>(wordList), vis = new HashSet<>();
            Queue<String> q = new LinkedList<>();
            q.offer(beginWord);
            for (int len = 1; !q.isEmpty(); len++) {
                for (int i = q.size(); i > 0; i--) {
                    String w = q.poll();
                    if (w.equals(endWord)) return len;
    
                    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;
                            ch[j] = c;
                            String nb = String.valueOf(ch);
                            if (dict.contains(nb) && vis.add(nb)) q.offer(nb);
                        }
                    }
                }
            }
            return 0;
        }
    

  • 3
    L

    Hey! I just want to thank you so much for actually explaining your solutions. Most people just copy and paste from their OJ but you actually take the time to explain. So thanks for that.


  • 0
    F

    @ssgg

    Test it just now,
    1-way BFS : 280ms
    2-way BFS : 80ms

    BTW, for 1-way BFS, a final return 0; is required for function int ladderLength()


  • 0
    F

    @cdai Thanks for sharing. The use of "dict.remove(next)" is very smart!


Log in to reply
 

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