2800-包含三个字符串的最短字符串

给你三个字符串 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 只包含小写英文字母。

下午两点【b站@灵茶山艾府】 直播讲题，欢迎关注！

---

暴力枚举 a,b,c 的全排列 a’,b’,c’，然后合并 a’,b’ 得到最短字符串 x，再合并 x,c’ 得到最短字符串 s。

可能有的同学觉得，a’,b’ 合并一个较长的会不会更优？

你可以这样理解：在没有完全包含的前提下，我们相当于在 b’ 的左边添加一些字母，右边添加一些字母，得到一个最短字符串 s。

可以先特判一下完全包含的情况，对于没有完全包含的情况，必然是合并得越短越好。

取最短且字典序最小的 s 作为答案。

[sol-Python3]

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

[sol-Go]

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 }

复杂度分析

• 时间复杂度：\mathcal{O}(n^2)，其中 n 为 a,b,c 的长度的最大值。
• 空间复杂度：\mathcal{O}(n)。