AI 助理
备案控制台
开发者社区 人工智能 文章 正文

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

2024-05-07 81
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【状态压缩 并集查找 图论】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 * 104

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++**实现。


文章标签：
云数据库 ClickHouse
算法
测试技术
C++
机器学习/深度学习
闻缺陷则喜何志丹
目录
相关文章
2025「AI安全」全球攻防赛小编
|
7天前
|
人工智能 自然语言处理 安全
双第一！阿里云领跑安全运营智能体
喜报～
2025「AI安全」全球攻防赛小编
2097 8
2025「AI安全」全球攻防赛小编
|
6天前
|
云安全 人工智能 安全
AI被攻击怎么办？
阿里云提供 AI 全栈安全能力，其中对网络攻击的主动识别、智能阻断与快速响应构成其核心防线，依托原生安全防护为客户筑牢免疫屏障。
2025「AI安全」全球攻防赛小编
1610 3
阿里云万网官方
|
15天前
|
域名解析 人工智能
【实操攻略】手把手教学，免费领取.CN域名
即日起至2025年12月31日，购买万小智AI建站或云·企业官网，每单可免费领1个.CN域名首年！跟我了解领取攻略吧~
阿里云万网官方
2029 9
阿里云云原生
|
10天前
|
安全 Java Android开发
深度解析 Android 崩溃捕获原理及从崩溃到归因的闭环实践
崩溃堆栈全是 a.b.c？Native 错误查不到行号？本文详解 Android 崩溃采集全链路原理，教你如何把“天书”变“说明书”。RUM SDK 已支持一键接入。
阿里云云原生
618 216
阿里云开发者
|
存储 人工智能 监控
从代码生成到自主决策：打造一个Coding驱动的“自我编程”Agent
本文介绍了一种基于LLM的“自我编程”Agent系统，通过代码驱动实现复杂逻辑。该Agent以Python为执行引擎，结合Py4j实现Java与Python交互，支持多工具调用、记忆分层与上下文工程，具备感知、认知、表达、自我评估等能力模块，目标是打造可进化的“1.5线”智能助手。
阿里云开发者
859 61
游客6mpq4uc7irdxi
|
8天前
|
人工智能 移动开发 自然语言处理
2025最新HTML静态网页制作工具推荐：10款免费在线生成器小白也能5分钟上手
晓猛团队精选2025年10款真正免费、无需编程的在线HTML建站工具，涵盖AI生成、拖拽编辑、设计稿转代码等多种类型，均支持浏览器直接使用、快速出图与文件导出，特别适合零基础用户快速搭建个人网站、落地页或企业官网。
游客6mpq4uc7irdxi
1307 157
1837601489925924
|
5天前
|
编解码 Linux 数据安全/隐私保护
教程分享免费视频压缩软件，免费视频压缩，视频压缩免费，附压缩方法及学习教程
教程分享免费视频压缩软件，免费视频压缩，视频压缩免费，附压缩方法及学习教程
1837601489925924
246 138
1837601489925924
|
7天前
|
存储 安全 固态存储
四款WIN PE工具，都可以实现U盘安装教程
Windows PE是基于NT内核的轻量系统，用于系统安装、分区管理及故障修复。本文推荐多款PE制作工具，支持U盘启动，兼容UEFI/Legacy模式，具备备份还原、驱动识别等功能，操作简便，适合新旧电脑维护使用。
1837601489925924
542 109

热门文章

最新文章

  • 1
    linux下ffmpeg安装
  • 2
    overleaf 插入图片，引用图片，图标标题Fig与文章引用Figure不一致解决
  • 3
    364 页 PyTorch 版《动手学深度学习》PDF 开源了（全中文，支持 Jupyter 运行）
  • 4
    阿里云上的几种数据备份方式
  • 5
    用深度神经网络修复H漫：看完这篇你就能眼中无码
  • 6
    MySQL · 引擎特性 · 像NOSQL那样使用MySQL
  • 7
    解决GitHub文件无法下载的问题
  • 8
    OpenSearch大模型实践之Havenask篇
  • 9
    SpringBoot整合Java Mail实现Outlook / Office365发送邮件
  • 10
    2019阿里云双11来袭,价格非常重要,但是懂得上云攻略更重要
  • 1
    AI Agent框架
    63
  • 2
    AI Agent：从工具到伙伴的智能进化
    72
  • 3
    计算机网络--TCP和UDP学习
    30
  • 4
    LBA-ECO ND-30 营养分析和气体通量，森林年代序列，巴西帕拉州
    30
  • 5
    2025年测试工程师的核心能力：掌握Dify工作流编排AI测试智能体
    60
  • 6
    有了解过 SpringBoot 的参数配置吗？
    53
  • 7
    分类模型校准：ROC-AUC不够？用ECE/pMAD评估概率质量
    24
  • 8
    把服务器当代码写：IaC 让部署变得又稳又香
    50
  • 9
    SDN 和 NFV：把网络“拆开重做”的底层革命，到底牛在哪？
    54
  • 10
    用数据“掘地三尺”，为零碳排放找出一条最靠谱的路
    33

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    阿里云弹性公网IP线路类型【BGP(多线)_精品】是什么意思？