Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

433. Minimum Genetic Mutation

Time: $O(n4^{\ell})$, where $n = |\texttt{bank}|$ and $\ell = |\texttt{word}|$

Space: $O(n)$

			


class Solution {
 public:
  int minMutation(string start, string end, vector<string>& bank) {
    unordered_set<string> bankSet{bank.begin(), bank.end()};
    if (!bankSet.count(end))
      return -1;

    int ans = 0;
    queue<string> q{{start}};

    while (!q.empty()) {
      ++ans;
      for (int sz = q.size(); sz > 0; --sz) {
        string word = q.front();
        q.pop();
        for (int j = 0; j < word.length(); ++j) {
          const char cache = word[j];
          for (const char c : {'A', 'C', 'G', 'T'}) {
            word[j] = c;
            if (word == end)
              return ans;
            if (bankSet.count(word)) {
              bankSet.erase(word);
              q.push(word);
            }
          }
          word[j] = cache;
        }
      }
    }

    return -1;
  }
};




			


class Solution {
  public int minMutation(String start, String end, String[] bank) {
    Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
    if (!bankSet.contains(end))
      return -1;

    int ans = 0;
    Queue<String> q = new ArrayDeque<>(Arrays.asList(start));

    while (!q.isEmpty()) {
      ++ans;
      for (int sz = q.size(); sz > 0; --sz) {
        StringBuilder sb = new StringBuilder(q.poll());
        for (int j = 0; j < sb.length(); ++j) {
          final char cache = sb.charAt(j);
          for (final char c : new char[] {'A', 'C', 'G', 'T'}) {
            sb.setCharAt(j, c);
            final String word = sb.toString();
            if (word.equals(end))
              return ans;
            if (bankSet.contains(word)) {
              bankSet.remove(word);
              q.offer(word);
            }
          }
          sb.setCharAt(j, cache);
        }
      }
    }

    return -1;
  }
}