C++_BFS method _ AC


  • 0
    class Solution {
    public:
    unordered_set<string> st;
    vector<char> letter = {'A', 'C', 'G', 'T'};
    int minMutation(string start, string end, vector<string>& bank) {
        if(bank.empty() || start.size() != end.size()) return -1;
        int res = 1;
        for(auto s : bank){st.insert(s);}
        queue<string> q;
        bfs(start, q);
        while(!q.empty()){
            int cur_size = q.size();
            for(int i = 0; i < cur_size; ++i){
                string s = q.front();
                q.pop();
                if(s == end) return res;
                bfs(s, q);
            }
            res++;
        }
        return -1;
    }
    
    void bfs(string start, queue<string>& q){
        st.erase(start);
        for(int i = 0; i < start.size(); ++i){
            char tmp = start[i];
            for(auto j : letter){
                if(tmp != j){
                    start[i] = j;
                    if(st.find(start) != st.end()){
                        q.push(start);
                        st.erase(start);
                    }
                }
            }
            start[i] = tmp;
        }
        return;
    }
    };

Log in to reply
 

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