{"id":9880,"date":"2022-10-31T10:25:21","date_gmt":"2022-10-31T17:25:21","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9880"},"modified":"2022-10-31T10:26:50","modified_gmt":"2022-10-31T17:26:50","slug":"leetcode-2452-words-within-two-edits-of-dictionary%ef%bf%bc","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-2452-words-within-two-edits-of-dictionary%ef%bf%bc\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2452.\u00a0Words Within Two Edits of Dictionary"},"content":{"rendered":"\n

You are given two string arrays, queries<\/code> and dictionary<\/code>. All words in each array comprise of lowercase English letters and have the same length.<\/p>\n\n\n\n

In one edit<\/strong> you can take a word from queries<\/code>, and change any letter in it to any other letter. Find all words from queries<\/code> that, after a maximum<\/strong> of two edits, equal some word from dictionary<\/code>.<\/p>\n\n\n\n

Return a list of all words from <\/em>queries<\/code>, <\/em>that match with some word from <\/em>dictionary<\/code> after a maximum of two edits<\/strong><\/em>. Return the words in the same order<\/strong> they appear in queries<\/code>.<\/p>\n\n\n\n

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

Input:<\/strong> queries = [\"word\",\"note\",\"ants\",\"wood\"], dictionary = [\"wood\",\"joke\",\"moat\"]\nOutput:<\/strong> [\"word\",\"note\",\"wood\"]\nExplanation:<\/strong>\n- Changing the 'r' in \"word\" to 'o' allows it to equal the dictionary word \"wood\".\n- Changing the 'n' to 'j' and the 't' to 'k' in \"note\" changes it to \"joke\".\n- It would take more than 2 edits for \"ants\" to equal a dictionary word.\n- \"wood\" can remain unchanged (0 edits) and match the corresponding dictionary word.\nThus, we return [\"word\",\"note\",\"wood\"].\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> queries = [\"yes\"], dictionary = [\"not\"]\nOutput:<\/strong> []\nExplanation:<\/strong>\nApplying any two edits to \"yes\" cannot make it equal to \"not\". Thus, we return an empty array.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= queries.length, dictionary.length <= 100<\/code><\/li>
  • n == queries[i].length == dictionary[j].length<\/code><\/li>
  • 1 <= n <= 100<\/code><\/li>
  • All queries[i]<\/code> and dictionary[j]<\/code> are composed of lowercase English letters.<\/li><\/ul>\n\n\n\n
    Solution: Hamming distance + Brute Force<\/strong><\/h2>\n\n\n\n
    For each query word q, check the hamming distance between it and all words in the dictionary.<\/p>\n\n\n\n
    Time complexity: O(|q|*|d|*n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector twoEditWords(vector& queries, vector& dictionary) {\n    const int n = queries[0].size();\n    auto check = [&](string_view q) {      \n      for (const string& w : dictionary) {\n        int dist = 0;\n        for (int i = 0; i < n && dist <= 3; ++i)\n          dist += q[i] != w[i];\n        if (dist <= 2) return true;\n      }\n      return false;\n    };\n    vector ans;\n    for (const string& q : queries) \n      if (check(q)) ans.push_back(q);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given two string arrays, queries and dictionary. All words in each array comprise of lowercase English letters and have the same length. In one edit you can take…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[787,188,177,4],"class_list":["post-9880","post","type-post","status-publish","format-standard","hentry","category-string","tag-edit-distance","tag-hamming-distance","tag-medium","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9880","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=9880"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9880\/revisions"}],"predecessor-version":[{"id":9883,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9880\/revisions\/9883"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9880"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9880"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9880"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}