包含三个字符串的最短字符串
给你三个字符串 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 只包含小写英文字母。\)
解题思路1：暴力解
本来考虑了蛮多的，但是看到这个100的长度，以及想了想周赛的排名，我又违背初心写下了这个暴力解。想法就是遍历所有的可能拼接方法：abc,acb,bac,bca......一共六种可能的拼接方法，从中选择一个最短的字典序最小的，关键在于拼接两个字符串，思考一下细节就可以写出来啦。那么时间复杂度就是\(O(12 \times n ^2)\),string的substr()方法的时间复杂度是O(length of substring)。
Code1
class Solution {
public:
//子串包含abc
//长度最短
//字典序最小
//暴力解法：遍历六种可能性
//关键在于拼接两个字符串
string concat(string &s1,string &s2)
{
string ans;
//s1的尾部和s2的头部重叠的数目
int dul = 0;
if(s1.size() > s2.size())
{
for(int i = 0;i <= s1.size() - s2.size();i ++)
{
if(s1.substr(i,s2.size()) == s2) return s1;
}
for(int i = 1;i <= s2.size();i ++)
if(s1.substr(s1.size() -i,i) == s2.substr(0,i))
dul = i;
}
else
{
for(int i = 1;i <= s1.size();i ++)
if(s1.substr(s1.size() - i,i) == s2.substr(0,i))
dul = i;
}
string res = s2.substr(dul,s2.size() - dul);
ans = s1 + res;
return ans;
}
string minimumString(string a, string b, string c) {
string ans = a + b + c;
string con1 = concat(a,b);
string con2 = concat(con1,c);
if(ans.size() > con2.size()) ans = con2;
else if(ans.size() == con2.size() && ans > con2) ans = con2;
con1 = concat(a,c);
con2 = concat(con1,b);
if(ans.size() > con2.size()) ans = con2;
else if(ans.size() == con2.size() && ans > con2) ans = con2;
con1 = concat(b,a);
con2 = concat(con1,c);
if(ans.size() > con2.size()) ans = con2;
else if(ans.size() == con2.size() && ans > con2) ans = con2;
con1 = concat(b,c);
con2 = concat(con1,a);
if(ans.size() > con2.size()) ans = con2;
else if(ans.size() == con2.size() && ans > con2) ans = con2;
con1 = concat(c,a);
con2 = concat(con1,b);
if(ans.size() > con2.size()) ans = con2;
else if(ans.size() == con2.size() && ans > con2) ans = con2;
con1 = concat(c,b);
con2 = concat(con1,a);
if(ans.size() > con2.size()) ans = con2;
else if(ans.size() == con2.size() && ans > con2) ans = con2;
return ans;
}
};