{"id":2340,"date":"2018-03-24T10:39:20","date_gmt":"2018-03-24T17:39:20","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2340"},"modified":"2018-03-24T10:44:34","modified_gmt":"2018-03-24T17:44:34","slug":"leetcode-433-minimum-genetic-mutation","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-433-minimum-genetic-mutation\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 433. Minimum Genetic Mutation"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e2a\u57fa\u56e0\u5e93\uff0c\u95ee\u4e00\u4e2a\u57fa\u56e0\u6700\u5c11\u9700\u8981\u53d8\u5f02\u591a\u5c11\u6b21\u624d\u80fd\u53d8\u4e3a\u53e6\u5916\u4e00\u4e2a\u57fa\u56e0\u3002\u6bcf\u6b21\u53d8\u5f02\u53ea\u80fd\u4fee\u6539\u4e00\u4e2a\u5b57\u7b26\uff0c\u5e76\u4e14\u5fc5\u987b\u5728\u57fa\u56e0\u5e93\u91cc\u3002<\/p>\n

https:\/\/leetcode.com\/problems\/minimum-genetic-mutation\/description\/<\/a><\/p>\n

A gene string can be represented by an 8-character long string, with choices from\u00a0\"A\"<\/code>,\u00a0\"C\"<\/code>,\u00a0\"G\"<\/code>,\u00a0\"T\"<\/code>.<\/p>\n

Suppose we need to investigate about a mutation (mutation from “start” to “end”), where ONE mutation is defined as ONE single character changed in the gene string.<\/p>\n

For example,\u00a0\"AACCGGTT\"<\/code>\u00a0->\u00a0\"AACCGGTA\"<\/code>\u00a0is 1 mutation.<\/p>\n

Also, there is a given gene “bank”, which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.<\/p>\n

Now, given 3 things – start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from “start” to “end”. If there is no such a mutation, return -1.<\/p>\n

Note:<\/b><\/p>\n

    \n
  1. Starting point is assumed to be valid, so it might not be included in the bank.<\/li>\n
  2. If multiple mutations are needed, all mutations during in the sequence must be valid.<\/li>\n
  3. You may assume start and end string is not the same.<\/li>\n<\/ol>\n

    Example 1:<\/b><\/p>\n

    start: \"AACCGGTT\"\r\nend:   \"AACCGGTA\"\r\nbank: [\"AACCGGTA\"]\r\n\r\nreturn: 1\r\n<\/pre>\n
    Example 2:<\/b><\/p>\n
    start: \"AACCGGTT\"\r\nend:   \"AAACGGTA\"\r\nbank: [\"AACCGGTA\", \"AACCGCTA\", \"AAACGGTA\"]\r\n\r\nreturn: 2\r\n<\/pre>\n
    Example 3:<\/b><\/p>\n
    start: \"AAAAACCC\"\r\nend:   \"AACCCCCC\"\r\nbank: [\"AAAACCCC\", \"AAACCCCC\", \"AACCCCCC\"]\r\n\r\nreturn: 3<\/pre>\n
    Solution: BFS Shortest Path<\/strong><\/h1>\n
    Time complexity: O(n^2)<\/p>\n
    Space complexity: O(n)<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 4 ms\r\nclass Solution {\r\npublic:\r\n  int minMutation(string start, string end, vector<string>& bank) {    \r\n    queue<string> q;\r\n    q.push(start);\r\n    \r\n    unordered_set<string> visited;\r\n    visited.insert(start);\r\n    \r\n    int mutations = 0;\r\n    while (!q.empty()) {\r\n      size_t size = q.size();\r\n      while (size--) {\r\n        string curr = std::move(q.front()); q.pop();\r\n        if (curr == end) return mutations;\r\n        for (const string& gene : bank) {\r\n          if (visited.count(gene) || !validMutation(curr, gene)) continue;\r\n          visited.insert(gene);\r\n          q.push(gene);\r\n        }\r\n      }\r\n      ++mutations;\r\n    }    \r\n    return -1;\r\n  }\r\nprivate:\r\n  bool validMutation(const string& s1, const string& s2) {\r\n    int count = 0;\r\n    for (int i = 0; i < s1.length(); ++i)\r\n      if (s1[i] != s2[i] && count++) return false;\r\n    return true;\r\n  }\r\n};<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Problem \u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e2a\u57fa\u56e0\u5e93\uff0c\u95ee\u4e00\u4e2a\u57fa\u56e0\u6700\u5c11\u9700\u8981\u53d8\u5f02\u591a\u5c11\u6b21\u624d\u80fd\u53d8\u4e3a\u53e6\u5916\u4e00\u4e2a\u57fa\u56e0\u3002\u6bcf\u6b21\u53d8\u5f02\u53ea\u80fd\u4fee\u6539\u4e00\u4e2a\u5b57\u7b26\uff0c\u5e76\u4e14\u5fc5\u987b\u5728\u57fa\u56e0\u5e93\u91cc\u3002 https:\/\/leetcode.com\/problems\/minimum-genetic-mutation\/description\/ A gene string can be represented by an 8-character long string, with choices from\u00a0“A”,\u00a0“C”,\u00a0“G”,\u00a0“T”. Suppose we need to investigate about a mutation…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76,47],"tags":[34,77,268,87],"class_list":["post-2340","post","type-post","status-publish","format-standard","hentry","category-graph","category-string","tag-bfs","tag-graph","tag-mutation","tag-shortest-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2340","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2340"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2340\/revisions"}],"predecessor-version":[{"id":2346,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2340\/revisions\/2346"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2340"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2340"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2340"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}