leetcode 433. Minimum Genetic Mutation | 433. 最小基因变化（图的DFS）-蒲公英云

leetcode 433. Minimum Genetic Mutation | 433. 最小基因变化（图的DFS）

题目

https://leetcode.com/problems/minimum-genetic-mutation/
在这里插入图片描述

题解

图的 DFS，思路见草稿：
在这里插入图片描述

class Solution { 
    int N;
    public int minMutation(String start, String end, String[] bank) { 
        // 去重
        HashSet<String> set = new HashSet<>(Arrays.asList(bank));
        bank = set.toArray(new String[0]);
        N = bank.length;
        // init graph
        Map<String, Set<String>> map = new HashMap<>();
        for (int i = 0; i < N; i++) { 
            if (!map.containsKey(bank[i])) { 
                Set<String> i2j = new HashSet<>();
                map.put(bank[i], i2j);
            }
            for (int j = i + 1; j < N; j++) { 
                if (!map.containsKey(bank[j])) { 
                    Set<String> j2i = new HashSet<>();
                    map.put(bank[j], j2i);
                }
                if (mutate(bank[i], bank[j])) { 
                    map.get(bank[i]).add(bank[j]);
                    map.get(bank[j]).add(bank[i]);
                }
            }
        }
        // dfs
        int min = Integer.MAX_VALUE;
        Set<String> visited = new HashSet<>();
        for (String s : bank) {  // start并未在bank[]中出现
            if (mutate(start, s)) { 
                visited.add(s);
                int distance = dfs(map, s, end, visited);
                if (distance > 0) min = Math.min(min, distance);
                visited.remove(s);
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
    // 当前start->end最短路径的长度
    public int dfs(Map<String, Set<String>> map, String start, String end, Set<String> visited) { 
        if (visited.size() == N) return start.equals(end) ? N : -1; // (剪枝)已走完全部路径
        if (start.equals(end)) return visited.size();
        int min = Integer.MAX_VALUE;
        for (String k : map.get(start)) { 
            if (!visited.contains(k)) { 
                visited.add(k);
                int distance = dfs(map, k, end, visited);
                if (distance > 0) min = Math.min(min, distance);
                visited.remove(k);
            }
        }
        return min;
    }
    public boolean mutate(String s1, String s2) { 
        int diff = 0;
        for (int i = 0; i < s1.length(); i++) { 
            if (s1.charAt(i) != s2.charAt(i)) { 
                if (++diff > 1) return false;
            }
        }
        return true;
    }
}