Concise C++ solution with only Queue (No other data structure used)


  • 6
    J
    class Solution {
    private:
        bool isOneDiff(const string& A, const string& B) {
            if (A.size() != B.size())
                return false;
            int diff = 0;
            for (int i = 0; i < A.size(); ++i) {
                if (A[i] != B[i])
                    ++diff;
                if (diff > 1)
                    return false;
            }
            return diff == 1;
        }
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& dict) {
            if (dict.count(beginWord) == 0 || dict.count(endWord) == 0)
                return 0;
    
            queue<pair<string, int> > que;
            que.push(make_pair(beginWord, 1));
            dict.erase(beginWord);
            
            while (!que.empty()) {
                pair<string, int> cur = que.front(); que.pop();
                for (auto it = dict.begin(); it != dict.end(); ) {
                    if (isOneDiff(cur.first, *it)) {
                        if (*it == endWord) return cur.second + 1;
                        que.push(make_pair(*it, cur.second + 1));
                        it = dict.erase(it);
                    } else ++it;
                }
            }
            return 0;
        }
    };

  • 4
    Y

    Actually I use the same method before, The performance is not good because traversal the whole dictionary waste more time than construct the string instead. Its very easy to get time limit exceeded.


  • 0
    D

    I think your solution is wrong as you are only assuming that endWord always do exist in the dictionary, that is not necessarily true.
    ie: in given test dict = {"hot","dot","dog","lot","log"}, startWord = "hit" and endWord = "cog".
    here your solution will return 0 while correct answer is 5.


  • 0
    O

    easily add endWord into the dictionary would be fine


Log in to reply
 

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