涉及知识点
有序集合 字符串
题目
给你三个字符串 a ，b 和 c ， 你的任务是找到长度 最短 的字符串，且这三个字符串都是它的 子字符串 。
如果有多个这样的字符串，请你返回 字典序最小 的一个。
请你返回满足题目要求的字符串。
注意：
两个长度相同的字符串 a 和 b ，如果在第一个不相同的字符处，a 的字母在字母表中比 b 的字母 靠前 ，那么字符串 a 比字符串 b 字典序小 。
子字符串 是一个字符串中一段连续的字符序列。
示例 1：
输入：a = “abc”, b = “bca”, c = “aaa”
输出：“aaabca”
解释：字符串 “aaabca” 包含所有三个字符串：a = ans[2…4] ，b = ans[3…5] ，c = ans[0…2] 。结果字符串的长度至少为 6 ，且"aaabca" 是字典序最小的一个。
示例 2：
输入：a = “ab”, b = “ba”, c = “aba”
输出：“aba”
解释：字符串 “aba” 包含所有三个字符串：a = ans[0…1] ，b = ans[1…2] ，c = ans[0…2] 。由于 c 的长度为 3 ，结果字符串的长度至少为 3 。“aba” 是字典序最小的一个。
参数范围：
1 <= a.length, b.length, c.length <= 100
a ，b ，c 只包含小写英文字母。
分析
合并两个字符串
假定a在前,b在后。有如下两种情况。
| a包括b | a=“ab”,b=“a”,合并后为"ab" |
| a的后缀和b的前缀相同，以下简称公共后前缀 | a=“ab”,b=“bc”，合并后"abc" |
分两部
| 第一步 | 第二步 |
| ab | abc |
| ab | c(ab) |
| ac | acb |
| ac | b(ac) |
| ba | bac |
| ba | c(ba) |
| bc | bca |
| bc | a(bc) |
| ca | cab |
| ca | b(ca) |
| cb | cba |
| cb | a(cb) |
| 共12种情况 |
abc和a(bc)相同
abc和a(bc)相比，效果相同或更好，所以无需考虑a(bc)等。
| bc是第一种情况 | abc就是ab,a(bc)也是 |
| ab是第一种情况 | 这种情况不符合，abc=ac a(bc)等于a(xc)，如果xc是的前缀是a的后缀，且比x长，那c也是后缀，两者节省的长度相同。如果xc的前缀不是a的后缀，则c的前缀有可能是a的后缀，这种情况下：abc优于a(bc)。 |
| ab和bc都是第二种情况 | abc = a减去ab公共后前缀+b+c减去bc公共后前缀 a(bc)也是 |
变量函数解释
| m_setStrs | 记录备选答案，自动根据长度和字典序排序 |
| next_permutation | 下一个顺序，初始要排序，使得初始最小序 |
代码
class Solution { public: string minimumString(string a, string b, string c) { vector<string> strs = { a,b,c }; sort(strs.begin(), strs.end()); do { string tmp = Union(strs[0], strs[1]); tmp = Union(tmp, strs[2]); m_setStrs.emplace(tmp.length(), tmp); } while (next_permutation(strs.begin(), strs.end())); return m_setStrs.begin()->second; } string Union(const string& a, const string& b) { if (-1 != a.find(b)) { return a; } int len = min(a.length(), b.length()); int i = len; for (; i > 0; i--) { if (a.substr(a.length() - i) == b.substr(0, i)) { break; } } return a.substr(0, a.length() - i) + b; } std::set<std::pair<int, string>> m_setStrs; };
旧版代码
class Solution { public: string minimumString(string a, string b, string c) { vector strs = { a,b,c }; sort(strs.begin(), strs.end()); if (-1 != strs[1].find(strs[0])) { strs[0] = “”; } if (-1 != strs[2].find(strs[1])) { strs[1] = “”; } do { Union(strs[0], strs[1], strs[2]); } while (next_permutation(strs.begin(), strs.end())); return m_setStrs.begin()->second; } void Union(const string& a, const string& b, const string& c) { string tmp = Union(a, b); tmp = Union(tmp, c); m_setStrs.emplace(tmp.length(), tmp); } string Union(const string& a, const string& b) { if (-1 != a.find(b)) { return a; } int len = min(a.length(), b.length()); int i = len; for (; i > 0; i–) { if (a.substr(a.length()-i)== b.substr(0,i)) { break; } } return a.substr(0, a.length() - i) + b; } std::set<std::pair<int, string>> m_setStrs; };
旧版代码二
class Solution { public: string minimumString(string a, string b, string c) { Union(a, b, c); Union(a, c, b); Union(b, a, c); Union(b, c, a); Union(c, a, b); Union(c, b, a); return m_setStrs.begin()->second; } void Union(const string& a, const string& b,const string& c) { string tmp = Union(a, b); tmp = Union(tmp, c); m_setStrs.emplace(tmp.length(),tmp); tmp = Union(b, c); tmp = Union(a, tmp); m_setStrs.emplace(tmp.length(), tmp); } string Union(const string& a, const string& b) { if (-1 != a.find(b)) { return a; } int len = min(a.length(), b.length()); int i = len; for (; i > 0; i–) { if (Same(a, b, i)) { break; } } return a.substr(0, a.length() - i) + b; } bool Same(const string& a, const string& b, int len) { for (int i = 0; i < len; i++) { if (a[a.length() - len + i] != b[i]) { return false; } } return true; } std::set<std::pair<int,string>> m_setStrs; };
2023年8月份代码
class Solution { public: string minimumString(string a, string b, string c) { Cat(a, b, c); Cat(a, c, b); Cat(b, a, c); Cat(b, c, a); Cat(c, a, b); Cat(c, b, a); string strRet = *m_setCan.begin(); for (const auto& it : m_setCan ) { if (it.length() < strRet.length()) { strRet = it; } } return strRet; } void Cat(string a, string b, string c) { std::set setCan; Cat(setCan, a, b); for (const auto& it : setCan) { Cat(m_setCan, it, c); } } void Cat(std::set& setCan,string a, string b) { int i = min(a.length(), b.length()); for (; i >= 1 ; i–) { const auto tmp1 = a.substr(a.length() - i); const auto tmp2 = b.substr(0, i); if (tmp1 == tmp2) { setCan.emplace(a + b.substr(i)); } } setCan.emplace(a + b); if (-1 != a.find(b)) { setCan.emplace(a); } } std::set m_setCan; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 洒家想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
