{"id":3714,"date":"2018-08-26T21:50:13","date_gmt":"2018-08-27T04:50:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3714"},"modified":"2018-08-30T09:25:13","modified_gmt":"2018-08-30T16:25:13","slug":"leetcode-893-groups-of-special-equivalent-strings","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-893-groups-of-special-equivalent-strings\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 893. Groups of Special-Equivalent Strings"},"content":{"rendered":"

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

You are given an array\u00a0A<\/code>\u00a0of strings.<\/p>\n

Two strings\u00a0S<\/code>\u00a0and\u00a0T<\/code>\u00a0are\u00a0special-equivalent<\/em>\u00a0if after any number of\u00a0moves<\/em>, S == T.<\/p>\n

A\u00a0move<\/em>\u00a0consists of choosing two indices\u00a0i<\/code>\u00a0and\u00a0j<\/code>\u00a0with\u00a0i % 2 == j % 2<\/code>, and swapping\u00a0S[i]<\/code>\u00a0with\u00a0S[j]<\/code>.<\/p>\n

Now, a\u00a0group of special-equivalent strings from\u00a0A<\/code><\/em>\u00a0is a\u00a0non-empty subset S of\u00a0A<\/code>\u00a0such that any string not in S\u00a0is not special-equivalent with any string in S.<\/p>\n

Return the number of groups of special-equivalent strings from\u00a0A<\/code>.<\/p>\n

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

Input: <\/strong>[\"a\",\"b\",\"c\",\"a\",\"c\",\"c\"]<\/span>\r\nOutput: <\/strong>3<\/span>\r\nExplanation<\/strong>: 3 groups [\"a\",\"a\"], [\"b\"], [\"c\",\"c\",\"c\"]\r\n<\/pre>\n
Example 2:<\/strong><\/p>\n
Input: <\/strong>[\"aa\",\"bb\",\"ab\",\"ba\"]<\/span>\r\nOutput: <\/strong>4<\/span>\r\nExplanation<\/strong>: 4 groups [\"aa\"], [\"bb\"], [\"ab\"], [\"ba\"]<\/span>\r\n<\/pre>\n
Example 3:<\/strong><\/p>\n
Input: <\/strong>[\"abc\",\"acb\",\"bac\",\"bca\",\"cab\",\"cba\"]<\/span>\r\nOutput: <\/strong>3<\/span>\r\nExplanation<\/strong>: 3 groups [\"abc\",\"cba\"], [\"acb\",\"bca\"], [\"bac\",\"cab\"]\r\n<\/pre>\n
Example 4:<\/strong><\/p>\n
Input: <\/strong>[\"abcd\",\"cdab\",\"adcb\",\"cbad\"]<\/span>\r\nOutput: <\/strong>1<\/span>\r\nExplanation<\/strong>: 1 group [\"abcd\",\"cdab\",\"adcb\",\"cbad\"]<\/span>\r\n<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  • 1 <= A.length <= 1000<\/code><\/li>\n
  • 1 <= A[i].length <= 20<\/code><\/li>\n
  • All\u00a0A[i]<\/code>\u00a0have the same length.<\/li>\n
  • All\u00a0A[i]<\/code>\u00a0consist of only lowercase letters.<\/li>\n<\/ul>\n
    \u00a0<\/ins><\/p>\n
    Solution: Signature<\/strong><\/h1>\n
    All Special-Equivalent Strings should have the same signature if we sort all the odd-index characters and all the even-index characters.<\/p>\n
    E.g.\u00a0[“abcd”,”cdab”,”adcb”,”cbad”] are all in the same graph.<\/p>\n
    “abcd”: odd “ac”, even: “bd”
    \n“cdab”: odd “ac”, even: “bd”
    \n“adcb”: odd “ac”, even: “bd”
    \n“cbad”: odd “ac”, even: “bd”<\/p>\n
    We can concatenate the odd and even strings to create a hashable signature.<\/p>\n
    Time complexity: O(n)<\/p>\n
    Space complexity: O(n)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 8 ms\r\nclass Solution {\r\npublic:\r\n  int numSpecialEquivGroups(vector<string>& A) {\r\n    unordered_set<string> s;\r\n    for (const string& a : A) {\r\n      string odd;\r\n      string even;\r\n      for (int i = 0; i < a.size(); ++i) {\r\n        if (i % 2)\r\n          odd += a[i];\r\n        else\r\n          even += a[i];\r\n      }\r\n      sort(begin(odd), end(odd));\r\n      sort(begin(even), end(even));\r\n      s.insert(odd + even);\r\n    }\r\n    return s.size();\r\n  }\r\n};<\/pre>\n\n<\/div>
    Java<\/h2>\n
    \n\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 16 ms\r\nclass Solution {\r\n  public int numSpecialEquivGroups(String[] A) {\r\n    Set<String> groups = new HashSet<>();\r\n    for (String a: A) {\r\n      char[] odd = new char[(a.length() + 1) \/ 2];\r\n      char[] even = new char[(a.length() + 1) \/ 2];\r\n      for (int i = 0; i < a.length(); ++i) {\r\n        if (i % 2 == 0)\r\n          even[i \/ 2] = a.charAt(i);\r\n        else\r\n          odd[i \/ 2] = a.charAt(i);          \r\n      }\r\n      Arrays.sort(odd);\r\n      Arrays.sort(even);\r\n      String s = new String(odd) + new String(even);\r\n      groups.add(s);\r\n    }\r\n    return groups.size();\r\n  }\r\n}<\/pre>\n\n<\/div>
    Python<\/h2>\n
    \n\n
    \"\"\"\r\nAuthor: Huahua\r\nRunning time: 56 ms\r\n\"\"\"\r\nclass Solution:\r\n  def numSpecialEquivGroups(self, A):\r\n    s = set()\r\n    for a in A:\r\n      odd = \"\"\r\n      even = \"\"\r\n      for i, c in enumerate(a):\r\n        if i % 2 == 0:\r\n          odd += c\r\n        else:\r\n          even += c      \r\n      s.add(''.join(sorted(odd) + sorted(even)))\r\n    return len(s)<\/pre>\n\n<\/div>
    Python (1-linear)<\/h2>\n
    \n\n
    \"\"\"\r\nAuthor: Huahua\r\nRunning time: 56 ms\r\n\"\"\"\r\nclass Solution:\r\n  def numSpecialEquivGroups(self, A):\r\n    return len(set([''.join(sorted(a[0::2]) + sorted(a[1::2])) for a in A]))<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem You are given an array\u00a0A\u00a0of strings. Two strings\u00a0S\u00a0and\u00a0T\u00a0are\u00a0special-equivalent\u00a0if after any number of\u00a0moves, S == T. A\u00a0move\u00a0consists of choosing two indices\u00a0i\u00a0and\u00a0j\u00a0with\u00a0i % 2 == j…<\/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":[222,82,388,4],"class_list":["post-3714","post","type-post","status-publish","format-standard","hentry","category-string","tag-easy","tag-hashtable","tag-signature","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3714","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=3714"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3714\/revisions"}],"predecessor-version":[{"id":3753,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3714\/revisions\/3753"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3714"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3714"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3714"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}