Skip to content

433. Minimum Genetic Mutation 👍

  • Time: $O(|\texttt{bank}| \cdot 4^{|\texttt{word}|})$
  • Space: $O(|\texttt{bank}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int minMutation(string startGene, string endGene, vector<string>& bank) {
    unordered_set<string> bankSet{bank.begin(), bank.end()};
    if (!bankSet.contains(endGene))
      return -1;

    constexpr char kGenes[] = "ACGT";
    queue<string> q{{startGene}};

    for (int step = 1; !q.empty(); ++step)
      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 : kGenes) {
            word[j] = c;
            if (word == endGene)
              return step;
            if (bankSet.contains(word)) {
              bankSet.erase(word);
              q.push(word);
            }
          }
          word[j] = cache;
        }
      }

    return -1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int minMutation(String startGene, String endGene, String[] bank) {
    Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
    if (!bankSet.contains(endGene))
      return -1;

    final char[] kGenes = new char[] {'A', 'C', 'G', 'T'};
    Queue<String> q = new ArrayDeque<>(List.of(startGene));

    for (int step = 1; !q.isEmpty(); ++step)
      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 : kGenes) {
            sb.setCharAt(j, c);
            final String word = sb.toString();
            if (word.equals(endGene))
              return step;
            if (bankSet.contains(word)) {
              bankSet.remove(word);
              q.offer(word);
            }
          }
          sb.setCharAt(j, cache);
        }
      }

    return -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def minMutation(self, startGene: str, endGene: str, bank: list[str]) -> int:
    bankSet = set(bank)
    if endGene not in bankSet:
      return -1

    kGenes = 'ACGT'
    q = collections.deque([startGene])

    step = 1
    while q:
      for _ in range(len(q)):
        wordList = list(q.popleft())
        for j, cache in enumerate(wordList):
          for c in kGenes:
            wordList[j] = c
            word = ''.join(wordList)
            if word == endGene:
              return step
            if word in bankSet:
              bankSet.remove(word)
              q.append(word)
          wordList[j] = cache
      step += 1

    return -1