{"id":9428,"date":"2022-01-17T19:12:42","date_gmt":"2022-01-18T03:12:42","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9428"},"modified":"2022-01-17T19:13:04","modified_gmt":"2022-01-18T03:13:04","slug":"leetcode-2135-count-words-obtained-after-adding-a-letter","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-2135-count-words-obtained-after-adding-a-letter\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2135. Count Words Obtained After Adding a Letter"},"content":{"rendered":"\n

You are given two 0-indexed<\/strong> arrays of strings startWords<\/code> and targetWords<\/code>. Each string consists of lowercase English letters<\/strong> only.<\/p>\n\n\n\n

For each string in targetWords<\/code>, check if it is possible to choose a string from startWords<\/code> and perform a conversion operation<\/strong> on it to be equal to that from targetWords<\/code>.<\/p>\n\n\n\n

The conversion operation<\/strong> is described in the following two steps:<\/p>\n\n\n\n

  1. Append<\/strong> any lowercase letter that is not present<\/strong> in the string to its end.
    • For example, if the string is \"abc\"<\/code>, the letters 'd'<\/code>, 'e'<\/code>, or 'y'<\/code> can be added to it, but not 'a'<\/code>. If 'd'<\/code> is added, the resulting string will be \"abcd\"<\/code>.<\/li><\/ul><\/li>
    • Rearrange<\/strong> the letters of the new string in any<\/strong> arbitrary order.
      • For example, \"abcd\"<\/code> can be rearranged to \"acbd\"<\/code>, \"bacd\"<\/code>, \"cbda\"<\/code>, and so on. Note that it can also be rearranged to \"abcd\"<\/code> itself.<\/li><\/ul><\/li><\/ol>\n\n\n\n

        Return the number of strings<\/strong> in <\/em>targetWords<\/code> that can be obtained by performing the operations on any<\/strong> string of <\/em>startWords<\/code>.<\/p>\n\n\n\n

        Note<\/strong> that you will only be verifying if the string in targetWords<\/code> can be obtained from a string in startWords<\/code> by performing the operations. The strings in startWords<\/code> do not<\/strong> actually change during this process.<\/p>\n\n\n\n

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

        Input:<\/strong> startWords = [\"ant\",\"act\",\"tack\"], targetWords = [\"tack\",\"act\",\"acti\"]\nOutput:<\/strong> 2\nExplanation:<\/strong>\n- In order to form targetWords[0] = \"tack\", we use startWords[1] = \"act\", append 'k' to it, and rearrange \"actk\" to \"tack\".\n- There is no string in startWords that can be used to obtain targetWords[1] = \"act\".\n  Note that \"act\" does exist in startWords, but we must<\/strong> append one letter to the string before rearranging it.\n- In order to form targetWords[2] = \"acti\", we use startWords[1] = \"act\", append 'i' to it, and rearrange \"acti\" to \"acti\" itself.\n<\/pre>\n\n\n\n
        Example 2:<\/strong><\/p>\n\n\n\n
        Input:<\/strong> startWords = [\"ab\",\"a\"], targetWords = [\"abc\",\"abcd\"]\nOutput:<\/strong> 1\nExplanation:<\/strong>\n- In order to form targetWords[0] = \"abc\", we use startWords[0] = \"ab\", add 'c' to it, and rearrange it to \"abc\".\n- There is no string in startWords that can be used to obtain targetWords[1] = \"abcd\".\n<\/pre>\n\n\n\n
        Constraints:<\/strong><\/p>\n\n\n\n
        • 1 <= startWords.length, targetWords.length <= 5 * 104<\/sup><\/code><\/li>
        • 1 <= startWords[i].length, targetWords[j].length <= 26<\/code><\/li>
        • Each string of startWords<\/code> and targetWords<\/code> consists of lowercase English letters only.<\/li>
        • No letter occurs more than once in any string of startWords<\/code> or targetWords<\/code>.<\/li><\/ul>\n\n\n\n
          Solution: Bitmask w\/ Hashtable<\/strong><\/h2>\n\n\n\n
          Since there is no duplicate letters in each word, we can use a bitmask to represent a word.<\/p>\n\n\n\n
          Step 1: For each word in startWords, we obtain its bitmask and insert it into a hashtable.
          Step 2: For each word in targetWords, enumerate it’s letter and unset 1 bit (skip one letter) and see whether it’s in the hashtable or not.<\/p>\n\n\n\n
          E.g. for target word “abc”, its bitmask is 0…0111, and we test whether “ab” or “ac” or “bc” in the hashtable or not.<\/p>\n\n\n\n
          Time complexity: O(n * 26^2)
          Space complexity: O(n * 26)<\/p>\n\n\n\n
          \n
          C++<\/h2>\n
          \n\n
          \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int wordCount(vector& startWords, vector& targetWords) {\n    unordered_set s;\n    auto getKey = [](const string& s) {      \n      return accumulate(begin(s), end(s), 0, [](int key, char c) { return key | (1 << (c - 'a')); });\n    };\n    \n    for (const string& w : startWords)\n      s.insert(getKey(w));\n        \n    return accumulate(begin(targetWords), end(targetWords), 0, [&](int ans, const string& w) {\n      const int key = getKey(w);\n      return ans + any_of(begin(w), end(w), [&](char c) { return s.count(key ^ (1 << (c - 'a'))); });\n    });\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
          You are given two 0-indexed arrays of strings startWords and targetWords. Each string consists of lowercase English letters only. For each string in targetWords, check if it is possible to choose a string…<\/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":[621,82,177,4],"class_list":["post-9428","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-bitmask","tag-hashtable","tag-medium","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9428","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=9428"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9428\/revisions"}],"predecessor-version":[{"id":9430,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9428\/revisions\/9430"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9428"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9428"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9428"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}