MinimumGeneticMutation.java

package dev.namtx.leetcode.daily;

/**
 * https://leetcode.com/problems/minimum-genetic-mutation
 */
public class MinimumGeneticMutation {
    public int minMutation(String start, String end, String[] bank) {
        boolean[] checked = new boolean[bank.length];
        int min = minMutation(start, end, bank, checked, 0);
        if (min == Integer.MAX_VALUE) return -1;
        return min;
    }

    private int minMutation(String start, String end, String[] bank, boolean[] checked, int mutations) {
        if (start.equals(end)) return mutations;

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < bank.length; i++) {
            if (!checked[i] && isMutation(bank[i], start)) {
                checked[i] = true;
                min = Math.min(min, minMutation(bank[i], end, bank, checked, mutations + 1));
                checked[i] = false;
            }
        }

        return min;
    }

    private boolean isMutation(String start, String end) {
        int diff = 0;
        for (int i = 0; i < start.length(); i++) {
            if (start.charAt(i) != end.charAt(i)) diff++;
        }

        return diff == 1;
    }
}

WordsWithinTwoEditsOfDictionary.java

package dev.namtx.leetcode.contest;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.com/contest/biweekly-contest-90/problems/words-within-two-edits-of-dictionary/
 */
public class WordsWithinTwoEditsOfDictionary {
    static class TrieNode {
        public Map<Character, TrieNode> children;
        public boolean isEndOfWord;
        public char character;

        public TrieNode(char c) {
            children = new HashMap<>();
            isEndOfWord = false;
            character = c;
        }
    }

    static class Trie {
        public TrieNode root;

        public Trie() {
            root = new TrieNode(' ');
        }

        public void addWord(String word) {
            TrieNode current = root;
            for (char c : word.toCharArray()) {
                if (!current.children.containsKey(c)) {
                    current.children.put(c, new TrieNode(c));
                }
                current = current.children.get(c);
            }
            current.isEndOfWord = true;
        }
    }

    public List<String> twoEditWords(String[] queries, String[] dictionary) {
        Trie trie = new Trie();
        for (String word : dictionary) {
            trie.addWord(word);
        }

        List<String> ans = new ArrayList<>();
        for (String query : queries) {
            if (twoEditWord(query, trie.root, 0, 0)) {
                ans.add(query);
            }
        }

        return ans;
    }

    public boolean twoEditWord(String word, TrieNode root, int i, int edit) {
        if (edit > 2) return false;
        if (i >= word.length()) return root.isEndOfWord;
        for (Map.Entry<Character, TrieNode> e : root.children.entrySet()) {
            if (twoEditWord(word, e.getValue(), i + 1, edit + (e.getKey() == word.charAt(i) ? 0 : 1))) {
                return true;
            }
        }

        return false;
    }
}