C++ BFS unordered_set queue


  • 0
    J
    class Solution {
    public:
        int minMutation(string start, string end, vector<string>& bank) {
            unordered_set<string> st;
            bool exist=false;
            for(auto bk: bank)
            {
               st.insert(bk);
            }
            if(st.find(end) == st.end())
            {
                return -1;
            }
            int ans=bank.size();
            queue<pair<string, int>> Q;
            Q.push({start, 0});
            
            while(!Q.empty())
            {
                int len=Q.size();
                for(int i=0; i<len; i++)
                {
                    auto curP=Q.front();
                    Q.pop();
                    int curstep=curP.second;
                    string curstr=curP.first;
                    for(auto bk: st)
                    {
                        if(OnlyOneDiff(bk, curstr))
                        {
                        
                            if(bk == end)
                            {
                                return curstep+1;
                            }
                            else
                            {
                                Q.push({bk, curstep+1});
                                st.erase(curstr);
                            }
                        }
                    }
                }
            }
            
            return ans>=bank.size()?-1:ans;
        }
        
        bool OnlyOneDiff(string a, string b)
        {
            int count=0;
            if(a.length() != b.length())
                return false;
            for(int i=0; i<a.length(); i++)
            {
                if(a[i] != b[i])
                    count++;
                if(count>=2)
                    return false;
            }
            return count==1;
        }
    };
    

Log in to reply
 

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