C++ BFS - does not use 'ACGT' in looping


  • 0
    M

    This solution is based on BFS as many suggested solutions here, but uses a different methodology when when finding candidate strings in the next layer.

    To find next-layer candidate strings during BFS, the most suggested method I saw here:

    • Go through the current string character by character, substitute each character by 'A', 'C', 'G', and 'T', see if it is in the bank (if true, add to next layer, and if it is end string return the current layer number).

    To find next-layer candidate strings during BFS, this solution:

    • For the current string, go through each string in bank, see if current string can mutate to this bank string (if true, add to next layer and if it is end string return the current layer number).

    Some notes:

    1. For this algorithm to be efficient, we need to compute and save the "mutation matrix", cell (i, j) meaning if string[i] can mutate to string[j] (note that matrix[j][i]==matrix[i][j]).

    2. To improve efficiency, mark each string as visited after visit it

    class Solution {
    public:
        int minMutation(string start, string end, vector<string>& bank) {
            if(start.size()!=end.size()) return -1; // corner case
            if(start.empty() || start==end) return 0; // corner case
            
            bank.push_back(start);
            
            int n = bank.size();
            vector<vector<bool>> valid(n, vector<bool>(n, false));
            for(int i=0; i<n; i++) {
                for(int j=i+1; j<n; j++) {
                    valid[i][j] = isValidMutate(bank[i], bank[j]);
                    valid[j][i] = valid[i][j];
                }
            }
            
            vector<bool> visited(n, false);
            queue<int> q1, q2;
            q1.push(n-1);
            visited[n-1]=true;
            int count = 0;
            
            while(!q1.empty()) {
                ++count;
                while(!q1.empty()) {
                    int i = q1.front();
                    q1.pop();
                    for(int j=0; j<n; j++) {
                        if(!visited[j] && valid[i][j]) {
                            if(bank[j]==end) return count;
                            q2.push(j);
                            visited[j]=true;
                        }
                    }
                }
                swap(q1,q2);
            }
            
            return -1;
            
        }
    private:
        bool isValidMutate(const string& s1, const string& s2) {
            if(s1.length() != s2.length()) return false;
            bool differ = false;
            for(int i=0; i<s1.length(); i++) {
                if(s1[i]!=s2[i]) {
                    if(differ) return false;
                    differ=true;
                }
            }
            return true;
        }
    };
    

Log in to reply
 

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