C++ Test Case Issue


  • 0
    D

    "AACCGGTT"
    "AAACGGTA"
    ["AACCGATT","AACCGATA","AAACGATA","AAACGGTA"]

    For the above test case my code below is working fine when I run on my computer, and outputs 4.
    But gives -1 when run on the OJ. Please help me...

    $ g++ minimum_genetic_mutation.cpp -std=c++11
    $ ./a.out

    #include <iostream>
    #include <vector>
    #include <queue>
    #include <string>
    
    using namespace std;
    
    class Solution {
    private:
    struct QItem{
      string geneSeq;
      int len;
      QItem(string s, int l) : geneSeq(s), len(l) {}
    };
    
    bool IsAdjacent(string &a, string &b) {
      int count = 0;
      for (int i = 0; i < a.length(); i++) {
        if (a[i] != b[i])
          count++;
        if (count == 2)
          return false;
      }
      return count == 1;
    }
    
    public:
      int minMutation(string start, string end, vector<string> &bank) {
        queue<QItem> q;
        q.push(QItem(start, 0));
        vector<bool> visited(false, bank.size()); // no need to initialize visited for start because it's not in the array
    
        while (!q.empty()) {
          QItem item = q.front();
          q.pop();
          for (int i = 0; i < bank.size(); i++) {
            if (!visited[i] && IsAdjacent(item.geneSeq, bank[i])) {
              if (bank[i] == end)
                return item.len + 1;
    
              visited[i] = true;
              q.push(QItem(bank[i], item.len + 1));
            }
          }
        }
    
        return -1;
      }
    };
    
    int main(int argc, char *argv[]) {
      string start = "AACCGGTT";
      string end = "AAACGGTA";
      vector<string> v = {"AACCGATT","AACCGATA","AAACGATA","AAACGGTA"};
      Solution s;
      cout << s.minMutation(start, end, v) << endl;
      return 0;
    }
    

Log in to reply
 

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