class Solution {
public:
string minimumString(string a, string b, string c) {
}
};
6918. 包含三个字符串的最短字符串
给你三个字符串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 <= 100a ，b ，c 只包含小写英文字母。原站题解
java 解法, 执行用时: 34 ms, 内存消耗: 43 MB, 提交时间: 2023-07-31 11:31:55
/**
* 1、模拟出所有的拼接情况；
* 2、【核心点】在于拼接的时候优化，如果被拼接的字符串包含在内就不拼接；
* 3、如果不包含则连接且连接时去掉重叠的部分；
* 4、然后从所有的拼接结果中获取到最佳的答案；
*/
class Solution {
public String minimumString(String a, String b, String c) {
// 全排列，6种
String s1 = join(join(a, b), c);
String s2 = join(join(a, c), b);
String s3 = join(join(b, a), c);
String s4 = join(join(b, c), a);
String s5 = join(join(c, a), b);
String s6 = join(join(c, b), a);
String res = s1;
for (String str : Arrays.asList(s1, s2, s3, s4, s5, s6)) {
if (str.length() < res.length()) {
res = str;
} else if (str.length() == res.length() && str.compareTo(res) < 0) {
res = str;
}
}
return res;
}
// 包含就不连接
// 不包含则连接且连接时去掉重叠的部分
public String join(String a, String b) {
// 包含就不连接
if (a.contains(b)) return a;
// 尝试获取最大的重叠宽度 w
int w = Math.min(a.length(), b.length());
for (; w > 0; w--) {
// 验证字符串 a, b 重叠宽度是否为 w
if (a.endsWith(b.substring(0, w))) {
break;
}
}
return a + b.substring(w);
}
}
golang 解法, 执行用时: 32 ms, 内存消耗: 6.5 MB, 提交时间: 2023-07-31 11:29:13
func merge(s, t string) string {
// 先特判完全包含的情况
if strings.Contains(s, t) {
return s
}
if strings.Contains(t, s) {
return t
}
for i := min(len(s), len(t)); ; i-- {
// 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的
if s[len(s)-i:] == t[:i] {
return s + t[i:]
}
}
}
func minimumString(a, b, c string) (ans string) {
arr := []string{a, b, c}
// 枚举 arr 的全排列
for _, p := range [][]int{{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}} {
s := merge(merge(arr[p[0]], arr[p[1]]), arr[p[2]])
if ans == "" || len(s) < len(ans) || len(s) == len(ans) && s < ans {
ans = s
}
}
return
}
func min(a, b int) int { if b < a { return b }; return a }
python3 解法, 执行用时: 220 ms, 内存消耗: 16.1 MB, 提交时间: 2023-07-31 11:28:44
class Solution:
def minimumString(self, a: str, b: str, c: str) -> str:
def merge(s: str, t: str) -> str:
# 先特判完全包含的情况
if t in s: return s
if s in t: return t
for i in range(min(len(s), len(t)), 0, -1):
# 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的
if s[-i:] == t[:i]:
return s + t[i:]
return s + t
ans = ""
for a, b, c in permutations((a, b, c)):
s = merge(merge(a, b), c)
if ans == "" or len(s) < len(ans) or len(s) == len(ans) and s < ans:
ans = s
return ans