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

妖狐艹你老母 2022-09-04 00:46 142阅读 0赞

## 题目 ##

[https://leetcode.com/problems/minimum-genetic-mutation/][https_leetcode.com_problems_minimum-genetic-mutation]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

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

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;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_minimum-genetic-mutation]: https://leetcode.com/problems/minimum-genetic-mutation/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/67fe5b3d02ca486c9a9d73f4367b9cf5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/3b7eedcf099343a3b62609196accb778.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/2d9f67f2f0ef49e18d3efcca33ea06f4.png