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

🕗 发布于 2024-04-21 12:57 图论算法 c++ 力扣状态压缩

本文涉及知识点

状态压缩并集查找图论

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<<j) 表示字母集合存在 ‘a’+j 。
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);
}
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

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

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

原文地址：https://blog.csdn.net/he_zhidan/article/details/137834732

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：MFC中CPropertyPage与CDialogEx的作用是什么，有什么区别，什么情况下会需要继承这两个类？
下一篇：eggjs 日志记录配置记录

linux线程cp模型，posix信号量，线程池，线程封装，单例模型，懒汉饿汉实现方式，自旋锁，读者写者模型
前面的同步，我们并没有一个很好的场景来模拟同步，只是简单的将有序的现象输出出来；现在我们来讲解一个比较合理且常见的模型——生产者消费者模型；
阅读更多2024-09-07
Qt/C++开源项目 TCP服务器调试助手（源码分享+发布链接下载）
该TCP服务器调试助手是用于测试和监控基于TCP协议的网络通信工具，能够帮助开发者便捷地进行网络通信调试。通过简洁的界面设计，用户可以轻松配置、管理TCP端口的连接，收发消息并进行数据监控分析。123
阅读更多2024-09-07
vue3整合antv x6实现图编辑器快速入门
例如：在上面节点基础上，我们有一个新的需求：给节点加上右键菜单。X6 支持使用 SVG、HTML 来渲染节点内容，在此基础上，我们还可以使用 React、Vue 组件来渲染节点，这样在开发过程中会非常
阅读更多2024-09-07
linux使用samba共享目录，其他虚拟机和windows都可以访问
linux使用samba共享目录，其他虚拟机和windows都可以访问
阅读更多2024-09-07
Linux系统编程实现ls -l | wc -l指令
由于该指令是通过管道的形式实现的，所以我们要使用系统函数pipe。ls -l |wc -l的作用就是统计当前目录有多少文件。由于父子间通过管道实现，所以存在读写阻塞问题，不用担心僵尸进程的产生，所以可
阅读更多2024-09-07
MySQL表操作及约束
MySQL表操作及约束
阅读更多2024-09-07
1.2CubeMAX创建FREERTOS入门示例
内核参数设置，用户根据自己的实际应用来裁剪定制。：相关宏的定义，可以自建一些常量在工程中使用。User Constants（用户常量）：定时器和信号量的创建。：用于查看堆使用情况。：任务与队列
阅读更多2024-09-07
YOLOv9改进策略【注意力机制篇】| PSA极化自我关注：实现高质量像素回归
本文记录的是基于PSA注意力模块的YOLOv9目标检测方法研究。PSA模块。本文将其应用到YOLOv9的检测任务中，使模型能够更好地捕捉图像中的细节信息，以实现目标检测任务中准确识别和定位。
阅读更多2024-09-07
爆改YOLOv8|利用yolov10的SCDown改进yolov8-下采样
yolov8改进，yolov10, 下采样SCDown, 即插即用
阅读更多2024-09-07
PDF样本图册转换为一个链接，随时打开无需印刷
想象一下，您手中有一本厚重的样本图册，里面包含了丰富多样的内容，如产品介绍、项目方案、学术论文等。在过去，您需要逐一翻阅、筛选，甚至为了便于查看，不得不将其印刷出来。如今，借助先进的数字化技术，还能实
阅读更多2024-09-07

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

本文涉及知识点

LeetCode2157. 字符串分组

状态压缩

代码

核心代码

测试用例

测试用例

扩展阅读

视频课程

相关下载

测试环境

相关文章

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