{"id":3028,"date":"2018-07-08T11:10:51","date_gmt":"2018-07-08T18:10:51","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3028"},"modified":"2018-07-08T11:25:13","modified_gmt":"2018-07-08T18:25:13","slug":"leetcode-839-similar-string-groups","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-839-similar-string-groups\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 839. Similar String Groups"},"content":{"rendered":"

Problem<\/h1>\n

Two strings\u00a0X<\/code>\u00a0and\u00a0Y<\/code>\u00a0are similar if we can swap two letters (in different positions) of\u00a0X<\/code>, so that\u00a0it equals\u00a0Y<\/code>.<\/p>\n

For example,\u00a0\"tars\"<\/code>\u00a0and\u00a0\"rats\"<\/code>\u00a0are similar (swapping at positions\u00a00<\/code>\u00a0and\u00a02<\/code>), and\u00a0\"rats\"<\/code>\u00a0and\u00a0\"arts\"<\/code>\u00a0are similar, but\u00a0\"star\"<\/code>\u00a0is not similar to\u00a0\"tars\"<\/code>,\u00a0\"rats\"<\/code>, or\u00a0\"arts\"<\/code>.<\/p>\n

Together, these form two connected groups by similarity:\u00a0{\"tars\", \"rats\", \"arts\"}<\/code>\u00a0and\u00a0{\"star\"}<\/code>.\u00a0 Notice that\u00a0\"tars\"<\/code>\u00a0and\u00a0\"arts\"<\/code>\u00a0are in the same group even though they are not similar.\u00a0 Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.<\/p>\n

We are given a list\u00a0A<\/code>\u00a0of strings.\u00a0 Every string in\u00a0A<\/code>\u00a0is an anagram of every other string in\u00a0A<\/code>.\u00a0 How many groups are there?<\/p>\n

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

Input: <\/strong>[\"tars\",\"rats\",\"arts\",\"star\"]\r\nOutput: <\/strong>2<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. A.length <= 2000<\/code><\/li>\n
  2. A[i].length <= 1000<\/code><\/li>\n
  3. A.length * A[i].length <= 20000<\/code><\/li>\n
  4. All words in\u00a0A<\/code>\u00a0consist of lowercase letters only.<\/li>\n
  5. All words in\u00a0A<\/code>\u00a0have the same length and are anagrams of each other.<\/li>\n
  6. The judging time limit has been increased for this question.<\/li>\n<\/ol>\n
    Solution: Brute Force + Union Find<\/h1>\n
    Time Complexity: O(n^2 * L)<\/p>\n
    Space Complexity: O(n)<\/p>\n
    C++<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 230 ms (<99.08%)\r\nclass DSU {\r\npublic:\r\n  DSU(int size):size_(size), parent_(size), rank_(size) {\r\n    iota(begin(parent_), end(parent_), 0);\r\n  }\r\n  \r\n  int Find(int n) {\r\n    if (parent_[n] != n) \r\n      parent_[n] = Find(parent_[n]);\r\n    return parent_[n];\r\n  }\r\n  \r\n  void Union(int x, int y) {\r\n    int px = Find(x);\r\n    int py = Find(y);\r\n    if (px == py) return;\r\n    if (rank_[py] > rank_[px])\r\n      swap(px, py);\r\n    else if (rank_[py] == rank_[px])\r\n      ++rank_[px];\r\n    parent_[py] = px;\r\n    --size_;\r\n  }\r\n  \r\n  int Size() const {\r\n    return size_;\r\n  }\r\n  \r\nprivate:\r\n  int size_;\r\n  vector<int> ranks_;\r\n  vector<int> parent_;\r\n};\r\n\r\nclass Solution {\r\npublic:\r\n  int numSimilarGroups(vector<string>& A) {\r\n    DSU dsu(A.size());\r\n    for (int i = 0; i < A.size(); ++i)\r\n      for (int j = i + 1; j < A.size(); ++j)\r\n        if (similar(A[i], A[j]))\r\n          dsu.Union(i, j);\r\n    return dsu.Size();\r\n  }\r\nprivate:\r\n  bool similar(const string& a, const string& b) {\r\n    int diff = 0;\r\n    for (int i = 0; i < a.length(); ++i)\r\n      if (a[i] != b[i] && ++diff > 2) return false;    \r\n    return true;\r\n  }\r\n};<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Problem Two strings\u00a0X\u00a0and\u00a0Y\u00a0are similar if we can swap two letters (in different positions) of\u00a0X, so that\u00a0it equals\u00a0Y. For example,\u00a0“tars”\u00a0and\u00a0“rats”\u00a0are similar (swapping at positions\u00a00\u00a0and\u00a02), and\u00a0“rats”\u00a0and\u00a0“arts”\u00a0are similar,…<\/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":[217,4,113],"class_list":["post-3028","post","type-post","status-publish","format-standard","hentry","category-string","tag-hard","tag-string","tag-union-find","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3028","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=3028"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3028\/revisions"}],"predecessor-version":[{"id":3032,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3028\/revisions\/3032"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3028"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3028"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3028"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}