{"id":9492,"date":"2022-02-06T17:03:45","date_gmt":"2022-02-07T01:03:45","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9492"},"modified":"2022-02-06T17:04:29","modified_gmt":"2022-02-07T01:04:29","slug":"leetcode-2157-groups-of-strings","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-2157-groups-of-strings\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2157. Groups of Strings"},"content":{"rendered":"\n<p>You are given a&nbsp;<strong>0-indexed<\/strong>&nbsp;array of strings&nbsp;<code>words<\/code>. Each string consists of&nbsp;<strong>lowercase English letters<\/strong>&nbsp;only. No letter occurs more than once in any string of&nbsp;<code>words<\/code>.<\/p>\n\n\n\n<p>Two strings&nbsp;<code>s1<\/code>&nbsp;and&nbsp;<code>s2<\/code>&nbsp;are said to be&nbsp;<strong>connected<\/strong>&nbsp;if the set of letters of&nbsp;<code>s2<\/code>&nbsp;can be obtained from the set of letters of&nbsp;<code>s1<\/code>&nbsp;by any&nbsp;<strong>one<\/strong>&nbsp;of the following operations:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Adding exactly one letter to the set of the letters of&nbsp;<code>s1<\/code>.<\/li><li>Deleting exactly one letter from the set of the letters of&nbsp;<code>s1<\/code>.<\/li><li>Replacing exactly one letter from the set of the letters of&nbsp;<code>s1<\/code>&nbsp;with any letter,&nbsp;<strong>including<\/strong>&nbsp;itself.<\/li><\/ul>\n\n\n\n<p>The array&nbsp;<code>words<\/code>&nbsp;can be divided into one or more non-intersecting&nbsp;<strong>groups<\/strong>. A string belongs to a group if any&nbsp;<strong>one<\/strong>&nbsp;of the following is true:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>It is connected to&nbsp;<strong>at least one<\/strong>&nbsp;other string of the group.<\/li><li>It is the&nbsp;<strong>only<\/strong>&nbsp;string present in the group.<\/li><\/ul>\n\n\n\n<p>Note that the strings in&nbsp;<code>words<\/code>&nbsp;should be grouped in such a manner that a string belonging to a group cannot be connected to a string present in any other group. It can be proved that such an arrangement is always unique.<\/p>\n\n\n\n<p>Return&nbsp;<em>an array<\/em>&nbsp;<code>ans<\/code>&nbsp;<em>of size<\/em>&nbsp;<code>2<\/code>&nbsp;<em>where:<\/em><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>ans[0]<\/code>&nbsp;<em>is the&nbsp;<strong>total number<\/strong>&nbsp;of groups<\/em>&nbsp;<code>words<\/code>&nbsp;<em>can be divided into, and<\/em><\/li><li><code>ans[1]<\/code>&nbsp;<em>is the&nbsp;<strong>size of the largest<\/strong>&nbsp;group<\/em>.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> words = [\"a\",\"b\",\"ab\",\"cde\"]\n<strong>Output:<\/strong> [2,3]\n<strong>Explanation:<\/strong>\n- words[0] can be used to obtain words[1] (by replacing 'a' with 'b'), and words[2] (by adding 'b'). So words[0] is connected to words[1] and words[2].\n- words[1] can be used to obtain words[0] (by replacing 'b' with 'a'), and words[2] (by adding 'a'). So words[1] is connected to words[0] and words[2].\n- words[2] can be used to obtain words[0] (by deleting 'b'), and words[1] (by deleting 'a'). So words[2] is connected to words[0] and words[1].\n- words[3] is not connected to any string in words.\nThus, words can be divided into 2 groups [\"a\",\"b\",\"ab\"] and [\"cde\"]. The size of the largest group is 3.  \n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> words = [\"a\",\"ab\",\"abc\"]\n<strong>Output:<\/strong> [1,3]\n<strong>Explanation:<\/strong>\n- words[0] is connected to words[1].\n- words[1] is connected to words[0] and words[2].\n- words[2] is connected to words[1].\nSince all strings are connected to each other, they should be grouped together.\nThus, the size of the largest group is 3.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= words.length &lt;= 2 * 10<sup>4<\/sup><\/code><\/li><li><code>1 &lt;= words[i].length &lt;= 26<\/code><\/li><li><code>words[i]<\/code>&nbsp;consists of lowercase English letters only.<\/li><li>No letter occurs more than once in&nbsp;<code>words[i]<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Bitmask + DFS<\/strong><\/h2>\n\n\n\n<p>Use a bitmask to represent a string. Use dfs to find connected components.<\/p>\n\n\n\n<p>Time complexity: O(n*26<sup>2<\/sup>)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<int> groupStrings(vector<string>& words) {\n    unordered_map<int, int> m;\n    for (const string& w : words)\n      ++m[accumulate(begin(w), end(w), 0, [](int k, char c){ return k | (1 << (c - 'a')); })];\n    function<int(int)> dfs = [&](int mask) {\n      auto it = m.find(mask);\n      if (it == end(m)) return 0;\n      int ans = it->second;      \n      m.erase(it);\n      for (int i = 0; i < 26; ++i) {        \n        ans += dfs(mask ^ (1 << i));\n        for (int j = i + 1; j < 26; ++j)\n          if ((mask >> i & 1) != (mask >> j & 1))\n            ans += dfs(mask ^ (1 << i) ^ (1 << j));\n      }\n      return ans;\n    };\n    int size = 0;\n    int groups = 0;\n    while (!m.empty()) {\n      size = max(size, dfs(begin(m)->first));\n      ++groups;\n    }\n    return {groups, size};\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a&nbsp;0-indexed&nbsp;array of strings&nbsp;words. Each string consists of&nbsp;lowercase English letters&nbsp;only. No letter occurs more than once in any string of&nbsp;words. Two strings&nbsp;s1&nbsp;and&nbsp;s2&nbsp;are said&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[102,77,42,113],"class_list":["post-9492","post","type-post","status-publish","format-standard","hentry","category-searching","tag-connected-components","tag-graph","tag-search","tag-union-find","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9492","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=9492"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9492\/revisions"}],"predecessor-version":[{"id":9494,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9492\/revisions\/9494"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9492"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9492"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9492"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}