【状态压缩并集查找图论】2157. 字符串分组-阿里云开发者社区

本文涉及知识点

状态压缩并集查找图论

LeetCode2157. 字符串分组

给你一个下标从 0 开始的字符串数组 words 。每个字符串都只包含小写英文字母。words 中任意一个子串中，每个字母都至多只出现一次。

如果通过以下操作之一，我们可以从 s1 的字母集合得到 s2 的字母集合，那么我们称这两个字符串为关联的：

往 s1 的字母集合中添加一个字母。

从 s1 的字母集合中删去一个字母。

将 s1 中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。

数组 words 可以分为一个或者多个无交集的组。如果一个字符串与另一个字符串关联，那么它们应当属于同一个组。

注意，你需要确保分好组后，一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下，分组方案是唯一的。

请你返回一个长度为 2 的数组 ans ：

ans[0] 是 words 分组后的总组数。

ans[1] 是字符串数目最多的组所包含的字符串数目。

示例 1：

输入：words = [“a”,“b”,“ab”,“cde”]

输出：[2,3]

解释：

words[0] 可以得到 words[1] （将 ‘a’ 替换为 ‘b’）和 words[2] （添加 ‘b’）。所以 words[0] 与 words[1] 和 words[2] 关联。
words[1] 可以得到 words[0] （将 ‘b’ 替换为 ‘a’）和 words[2] （添加 ‘a’）。所以 words[1] 与 words[0] 和 words[2] 关联。
words[2] 可以得到 words[0] （删去 ‘b’）和 words[1] （删去 ‘a’）。所以 words[2] 与 words[0] 和 words[1] 关联。
words[3] 与 words 中其他字符串都不关联。
所以，words 可以分成 2 个组 [“a”,“b”,“ab”] 和 [“cde”] 。最大的组大小为 3 。
示例 2：
输入：words = [“a”,“ab”,“abc”]
输出：[1,3]
解释：
words[0] 与 words[1] 关联。
words[1] 与 words[0] 和 words[2] 关联。
words[2] 与 words[1] 关联。
由于所有字符串与其他字符串都关联，所以它们全部在同一个组内。
所以最大的组大小为 3 。
提示：

1 <= words.length <= 2 * 10⁴

1 <= words[i].length <= 26

words[i] 只包含小写英文字母。

words[i] 中每个字母最多只出现一次。

状态压缩

由于本题words[i] 只包括小写字母，且没有重复字母，我们可以对字母集合进行状态压缩, maks&(1<

mMask,key 表示某个字母集合 value是一个vector 记录words[i]的下标i。key和words[i]关联。

然后通过 key value建立并集查找。

注意：

一，key 必须是words中存在的字母集合。

二，(mask | (1 << j1)) ^ ( 1 << j2) 括号不能省略

三，建立并集查找时，只需要v[i]和v[i-1]连接，不需要两两连接。前者时间复杂度是O(n)，后者时间复杂度是O(nn)。

代码

核心代码

class CUnionFind
{
public:
  CUnionFind(int iSize) :m_vNodeToRegion(iSize)
  {
    for (int i = 0; i < iSize; i++)
    {
      m_vNodeToRegion[i] = i;
    }
    m_iConnetRegionCount = iSize;
  } 
  CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
  {
    for (int i = 0; i < vNeiBo.size(); i++) {
      for (const auto& n : vNeiBo[i]) {
        Union(i, n);
      }
    }
  }
  int GetConnectRegionIndex(int iNode)
  {
    int& iConnectNO = m_vNodeToRegion[iNode];
    if (iNode == iConnectNO)
    {
      return iNode;
    }
    return iConnectNO = GetConnectRegionIndex(iConnectNO);
  }
  void Union(int iNode1, int iNode2)
  {
    const int iConnectNO1 = GetConnectRegionIndex(iNode1);
    const int iConnectNO2 = GetConnectRegionIndex(iNode2);
    if (iConnectNO1 == iConnectNO2)
    {
      return;
    }
    m_iConnetRegionCount--;
    if (iConnectNO1 > iConnectNO2)
    {
      UnionConnect(iConnectNO1, iConnectNO2);
    }
    else
    {
      UnionConnect(iConnectNO2, iConnectNO1);
    }
  }
  bool IsConnect(int iNode1, int iNode2)
  {
    return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
  }
  int GetConnetRegionCount()const
  {
    return m_iConnetRegionCount;
  }
  vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
  {
    const int iNodeSize = m_vNodeToRegion.size();
    vector<int> vRet(iNodeSize);
    for (int i = 0; i < iNodeSize; i++)
    {
      vRet[GetConnectRegionIndex(i)]++;
    }
    return vRet;
  }
  std::unordered_map<int, vector<int>> GetNodeOfRegion()
  {
    std::unordered_map<int, vector<int>> ret;
    const int iNodeSize = m_vNodeToRegion.size();
    for (int i = 0; i < iNodeSize; i++)
    {
      ret[GetConnectRegionIndex(i)].emplace_back(i);
    }
    return ret;
  }
private:
  void UnionConnect(int iFrom, int iTo)
  {
    m_vNodeToRegion[iFrom] = iTo;
  }
  vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
  int m_iConnetRegionCount;
};
class Solution {
public:
  vector<int> groupStrings(vector<string>& words) {
    unordered_map<int, vector<int>> mMask;
    for (int i = 0; i < words.size(); i++) {
      int iMask = 0;
      for (const auto& ch : words[i]) {
        iMask |= (1 << (ch - 'a'));
      }
      mMask[iMask].emplace_back(i);
    }   
    for (const auto& [mask, tmp] : mMask) {
      auto AddNewMask = [&](int mask,const int iMask) {
        if (!mMask.count(iMask)) { return; }
        mMask[mask].emplace_back(mMask[iMask][0]);
      };
      for (int j = 0; j < 26; j++) {
        if (mask & (1 << j)) {
          AddNewMask(mask, mask ^ (1 << j));
        }
        else {
          AddNewMask(mask, mask | (1 << j));
        }
      }
      for (int j1 = 0; j1 < 26; j1++) {
        if (mask & (1 << j1)) { continue; }
        for (int j2 = 0; j2 < 26; j2++) {
          if (!(mask & (1 << j2))) { continue; }
          AddNewMask(mask, (mask | (1 << j1)) ^ ( 1 << j2));
        }
      }
    }
    CUnionFind uf(words.size());
    for (const auto& [mask, v] : mMask) {
      for (int i = 1; i < v.size(); i++) {
        uf.Union(v[i], v[i - 1]);
      }
    }
    auto m = uf.GetNodeOfRegion();
    vector<int> vRet = { (int)m.size() };
    int iMax = 0;
    for (const auto& [tmp, v] : m) {
      iMax = max(iMax, (int)v.size());
    }
    vRet.emplace_back(iMax);
    return vRet;
  }
};

测试用例

class CUnionFind
{
public:
  CUnionFind(int iSize) :m_vNodeToRegion(iSize)
  {
    for (int i = 0; i < iSize; i++)
    {
      m_vNodeToRegion[i] = i;
    }
    m_iConnetRegionCount = iSize;
  } 
  CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
  {
    for (int i = 0; i < vNeiBo.size(); i++) {
      for (const auto& n : vNeiBo[i]) {
        Union(i, n);
      }
    }
  }
  int GetConnectRegionIndex(int iNode)
  {
    int& iConnectNO = m_vNodeToRegion[iNode];
    if (iNode == iConnectNO)
    {
      return iNode;
    }
    return iConnectNO = GetConnectRegionIndex(iConnectNO);
  }
  void Union(int iNode1, int iNode2)
  {
    const int iConnectNO1 = GetConnectRegionIndex(iNode1);
    const int iConnectNO2 = GetConnectRegionIndex(iNode2);
    if (iConnectNO1 == iConnectNO2)
    {
      return;
    }
    m_iConnetRegionCount--;
    if (iConnectNO1 > iConnectNO2)
    {
      UnionConnect(iConnectNO1, iConnectNO2);
    }
    else
    {
      UnionConnect(iConnectNO2, iConnectNO1);
    }
  }
  bool IsConnect(int iNode1, int iNode2)
  {
    return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
  }
  int GetConnetRegionCount()const
  {
    return m_iConnetRegionCount;
  }
  vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
  {
    const int iNodeSize = m_vNodeToRegion.size();
    vector<int> vRet(iNodeSize);
    for (int i = 0; i < iNodeSize; i++)
    {
      vRet[GetConnectRegionIndex(i)]++;
    }
    return vRet;
  }
  std::unordered_map<int, vector<int>> GetNodeOfRegion()
  {
    std::unordered_map<int, vector<int>> ret;
    const int iNodeSize = m_vNodeToRegion.size();
    for (int i = 0; i < iNodeSize; i++)
    {
      ret[GetConnectRegionIndex(i)].emplace_back(i);
    }
    return ret;
  }
private:
  void UnionConnect(int iFrom, int iTo)
  {
    m_vNodeToRegion[iFrom] = iTo;
  }
  vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
  int m_iConnetRegionCount;
};
class Solution {
public:
  vector<int> groupStrings(vector<string>& words) {
    unordered_map<int, vector<int>> mMask;
    for (int i = 0; i < words.size(); i++) {
      int iMask = 0;
      for (const auto& ch : words[i]) {
        iMask |= (1 << (ch - 'a'));
      }
      mMask[iMask].emplace_back(i);
    }   
    for (const auto& [mask, tmp] : mMask) {
      auto AddNewMask = [&](int mask,const int iMask) {
        if (!mMask.count(iMask)) { return; }
        mMask[mask].emplace_back(mMask[iMask][0]);
      };
      for (int j = 0; j < 26; j++) {
        if (mask & (1 << j)) {
          AddNewMask(mask, mask ^ (1 << j));
        }
        else {
          AddNewMask(mask, mask | (1 << j));
        }
      }
      for (int j1 = 0; j1 < 26; j1++) {
        if (mask & (1 << j1)) { continue; }
        for (int j2 = 0; j2 < 26; j2++) {
          if (!(mask & (1 << j2))) { continue; }
          AddNewMask(mask, (mask | (1 << j1)) ^ ( 1 << j2));
        }
      }
    }
    CUnionFind uf(words.size());
    for (const auto& [mask, v] : mMask) {
      for (int i = 1; i < v.size(); i++) {
        uf.Union(v[i], v[i - 1]);
      }
    }
    auto m = uf.GetNodeOfRegion();
    vector<int> vRet = { (int)m.size() };
    int iMax = 0;
    for (const auto& [tmp, v] : m) {
      iMax = max(iMax, (int)v.size());
    }
    vRet.emplace_back(iMax);
    return vRet;
  }
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
    assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
    if (v1.size() != v2.size())
    {
        assert(false);
        return;
    }
    for (int i = 0; i < v1.size(); i++)
    {
        Assert(v1[i], v2[i]);
    }
}
int main()
{
  vector<string> words;
  {
    Solution sln;
    words = { "a", "b" };
    auto res = sln.groupStrings(words);
    Assert({ 1,2 }, res);
  }
  {
    Solution sln;
    words = { "a", "b", "ab", "cde" };
    auto res = sln.groupStrings(words);
    Assert({ 2,3 }, res);
  }
  {
    Solution sln;
    words = { "a","ab","abc" };
    auto res = sln.groupStrings(words);
    Assert({ 1,3 }, res);
  }
}

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。

【状态压缩并集查找图论】2157. 字符串分组

本文涉及知识点

LeetCode2157. 字符串分组

状态压缩

代码

核心代码

测试用例

测试用例

测试环境

热门文章

最新文章

相关电子书

【状态压缩 并集查找 图论】2157. 字符串分组

本文涉及知识点

LeetCode2157. 字符串分组

状态压缩

代码

核心代码

测试用例

测试用例

测试环境

热门文章

最新文章

相关电子书

【状态压缩并集查找图论】2157. 字符串分组