MinimumGeneticMutation.java

// https://leetcode.com/problems/minimum-genetic-mutation
// T: O(B)
// S: O(1)

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class MinimumGeneticMutation {
    private record Info(String mutation, int steps) {}

    private static final char[] GENES = new char[] {'A', 'G', 'C', 'T'};

    // n = length of string (8), m = possible number of characters
    // BFS, T: O(V + E) = O(nB + n^m * mn) S: O(n^m)
    public static int minMutation(String startGene, String endGene, String[] bank) {
        final Set<String> genePool = toSet(bank);
        if (!genePool.contains(endGene)) {
            return -1;
        }

        final Queue<Info> queue = new LinkedList<>() {{ add(new Info(startGene, 0)); }};
        final Set<String> visited = new HashSet<>();

        while (!queue.isEmpty()) {
            final Info info = queue.poll();
            if (visited.contains(info.mutation)) {
                continue;
            }
            visited.add(info.mutation);

            if (endGene.equals(info.mutation)) {
                return info.steps;
            }

            for (String neighbour : validMutations(genePool, info.mutation)) {
                queue.add(new Info(neighbour, info.steps + 1));
            }
        }

        return -1;
    }

    // T: O(|s|), S: O(|s|)
    private static List<String> validMutations(Set<String> genePool, String s) {
        final List<String> result = new ArrayList<>();
        for (int i = 0 ; i < s.length() ; i++) {
            for (char c : GENES) {
                final String mutation = s.substring(0, i) + c + s.substring(i + 1);
                if (genePool.contains(mutation)) {
                    result.add(mutation);
                }
            }
        }
        return result;
    }

    // T: O(nB) S: O(nB)
    private static Set<String> toSet(String[] bank) {
        final Set<String> set = new HashSet<>();
        Collections.addAll(set, bank);
        return set;
    }
}