{"id":4572,"date":"2018-12-30T12:45:36","date_gmt":"2018-12-30T20:45:36","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4572"},"modified":"2018-12-30T12:55:36","modified_gmt":"2018-12-30T20:55:36","slug":"leetcode-966-vowel-spellchecker","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-966-vowel-spellchecker\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 966. Vowel Spellchecker"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\"><strong>Problem<\/strong><\/h2>\n\n\n\n<p>Given a&nbsp;<code>wordlist<\/code>, we want to implement a spellchecker that converts a query word into a correct word.<\/p>\n\n\n\n<p>For a given&nbsp;<code>query<\/code>&nbsp;word, the spell checker handles two categories of spelling mistakes:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Capitalization: If the query matches a word in the wordlist (<strong>case-insensitive<\/strong>), then the query word is returned with the same case as the case in the wordlist.<ul><li>Example:&nbsp;<code>wordlist = [\"yellow\"]<\/code>,&nbsp;<code>query = \"YellOw\"<\/code>:&nbsp;<code>correct = \"yellow\"<\/code><\/li><li>Example:&nbsp;<code>wordlist = [\"Yellow\"]<\/code>,&nbsp;<code>query = \"yellow\"<\/code>:&nbsp;<code>correct = \"Yellow\"<\/code><\/li><li>Example:&nbsp;<code>wordlist = [\"yellow\"]<\/code>,&nbsp;<code>query = \"yellow\"<\/code>:&nbsp;<code>correct = \"yellow\"<\/code><\/li><\/ul><\/li><li>Vowel Errors: If after replacing the vowels (&#8216;a&#8217;, &#8216;e&#8217;, &#8216;i&#8217;, &#8216;o&#8217;, &#8216;u&#8217;) of the query word with any vowel individually, it matches a word in the wordlist (<strong>case-insensitive<\/strong>), then the query word is returned with the same case as the match in the wordlist.<ul><li>Example:&nbsp;<code>wordlist = [\"YellOw\"]<\/code>,&nbsp;<code>query = \"yollow\"<\/code>:&nbsp;<code>correct = \"YellOw\"<\/code><\/li><li>Example:&nbsp;<code>wordlist = [\"YellOw\"]<\/code>,&nbsp;<code>query = \"yeellow\"<\/code>:&nbsp;<code>correct = \"\"<\/code>&nbsp;(no match)<\/li><li>Example:&nbsp;<code>wordlist = [\"YellOw\"]<\/code>,&nbsp;<code>query = \"yllw\"<\/code>:&nbsp;<code>correct = \"\"<\/code>&nbsp;(no match)<\/li><\/ul><\/li><\/ul>\n\n\n\n<p>In addition, the spell checker operates under the following precedence rules:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>When the query exactly matches a word in the wordlist (<strong>case-sensitive<\/strong>), you should return the same word back.<\/li><li>When the query matches a word up to capitlization, you should return the first such match in the wordlist.<\/li><li>When the query matches a word up to vowel errors, you should return the first such match in the wordlist.<\/li><li>If the query has no matches in the wordlist, you should return the empty string.<\/li><\/ul>\n\n\n\n<p>Given some&nbsp;<code>queries<\/code>, return a&nbsp;list of words&nbsp;<code>answer<\/code>, where&nbsp;<code>answer[i]<\/code>&nbsp;is&nbsp;the correct word for&nbsp;<code>query = queries[i]<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>wordlist = [\"KiTe\",\"kite\",\"hare\",\"Hare\"], queries = [\"kite\",\"Kite\",\"KiTe\",\"Hare\",\"HARE\",\"Hear\",\"hear\",\"keti\",\"keet\",\"keto\"]\n<strong>Output: <\/strong>[\"kite\",\"KiTe\",\"KiTe\",\"Hare\",\"hare\",\"\",\"\",\"KiTe\",\"\",\"KiTe\"]<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= wordlist.length &lt;= 5000<\/code><\/li><li><code>1 &lt;= queries.length &lt;= 5000<\/code><\/li><li><code>1 &lt;= wordlist[i].length &lt;= 7<\/code><\/li><li><code>1 &lt;= queries[i].length &lt;= 7<\/code><\/li><li>All strings in&nbsp;<code>wordlist<\/code>&nbsp;and&nbsp;<code>queries<\/code>&nbsp;consist only of&nbsp;<strong>english<\/strong>&nbsp;letters.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution:&nbsp;HashTable<\/strong><\/h2>\n\n\n\n<p>Using 3 hashtables: original words, lower cases, lower cases with vowels replaced to &#8220;*&#8221;<\/p>\n\n\n\n<p>Time complexity: O(|W|+|Q|)<br>Space complexity: O(|W|)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {    \n    vector<string> ans;\n    unordered_map<string, string> m_org;\n    unordered_map<string, string> m_low;\n    unordered_map<string, string> m_vow;\n    for (const string& w : wordlist) {\n      \/\/ Original word\n      m_org[w] = w;\n      \/\/ Case-insensitive\n      string l = toLower(w); \n      if (!m_low.count(l)) m_low[l] = w; \n      \/\/ Vowel-insensitive\n      string o = replaceVowels(l);\n      if (!m_vow.count(o)) m_vow[o] = w;\n    }\n    \n    for (const string& q : queries) {      \n      if (m_org.count(q)) {\n        ans.push_back(q);\n        continue;\n      }\n      string l = toLower(q);\n      if (m_low.count(l)) {\n        ans.push_back(m_low[l]);\n        continue;\n      }\n      \n      string o = replaceVowels(l);      \n      if (m_vow.count(o)) {\n        ans.push_back(m_vow[o]);\n        continue;\n      }\n      ans.push_back(\"\");\n    }\n    return ans;\n  }\nprivate:\n  string toLower(const string& s) {\n    string l(s);\n    std::transform(begin(s), end(s), begin(l), ::tolower);\n    return l;\n  }\n  \n  string replaceVowels(const string& s) {\n    string o(s);\n    for (char& c : o)\n      if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')\n        c = '*';\n    return o;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\nclass Solution:\n  def spellchecker(self, wordlist, queries):\n    org = dict()\n    low = dict()\n    vow = dict()\n    for w in wordlist:\n      org[w] = w\n      l = w.lower()\n      if l not in low: low[l] = w\n      v = re.sub(r'[aeiou]', '*', l)\n      if v not in vow: vow[v] = w\n    ans = []\n    for q in queries:\n      if q in org: \n        ans.append(q)\n        continue\n      l = q.lower()\n      if l in low:\n        ans.append(low[l])\n        continue\n      v = re.sub(r'[aeiou]', '*', l)\n      if v in vow:\n        ans.append(vow[v])\n        continue\n      ans.append(\"\")\n    return ans\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem Given a&nbsp;wordlist, we want to implement a spellchecker that converts a query word into a correct word. For a given&nbsp;query&nbsp;word, the spell checker handles&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[82,177,4,449],"class_list":["post-4572","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-medium","tag-string","tag-vowel","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4572","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=4572"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4572\/revisions"}],"predecessor-version":[{"id":4576,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4572\/revisions\/4576"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4572"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4572"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4572"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}