给你三个字符串 a ，b 和 c ， 你的任务是找到长度 最短 的字符串，且这三个字符串都是它的 子字符串 。

如果有多个这样的字符串，请你返回 字典序最小 的一个。

请你返回满足题目要求的字符串。

注意：

  • 两个长度相同的字符串 a 和 b ，如果在第一个不相同的字符处，a 的字母在字母表中比 b 的字母 靠前 ，那么字符串 a 比字符串 b 字典序小 。
  • 子字符串 是一个字符串中一段连续的字符序列。

 

示例 1：

输入：a = "abc", b = "", c = "aaa"
输出："aaa"
解释：字符串 "aaa" 包含所有三个字符串：a = ans[2...4] ，b = ans[3..5] ，c = ans[0..2] 。结果字符串的长度至少为 6 ，且"aaa" 是字典序最小的一个。

示例 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 只包含小写英文字母。

思路分析

时间复杂度 O(),其中为,, 的长度的最大值。

AC代码暴力枚举

通过去枚举,,,,,6种情况，考虑任意2个字符一前一后是否可以拼接
代码缺点：
1、用去枚举不如暴力枚举6种情况
2、判断2个字符串是否是前后缀没考虑a in b 和b in a(WA的原因)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def minimumString(self, a: str, b: str, c: str) -> str:
        def find(a:str,b:str):
            x = min(len(a),len(b))
            for i in range(x,-1,-1):
                if a[-i:] == b[:i]:
                    return i
            return 0

        def dfs(x,deep):
            if deep == 2:
                ans.append((len(x),x))
            for i in range(len(s)):
                if not visited[i]:
                    visited[i] = True
                    if s[i] in x:
                        dfs(x,deep+1)
                    else:
                        t = find(x,s[i])
                        tt = find(s[i],x)
                        dfs(x + s[i][t:],deep+1)
                        dfs(s[i] + x[tt:],deep+1)
                    visited[i] = False         

        s = [a,b,c]
        res = ''
        visited = [False,False,False]
        ans = []
        for i,x in enumerate(s):
            visited[i] = True
            dfs(x,0)
            visited[i] = False
        ans.sort(key = lambda x:(x[0],x[1]))
        return ans[0][1]

优化暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minimumString(self, a: str, b: str, c: str) -> str:
        def find(a:str,b:str):
            if a in b:
                return b
            if b in a:
                return a
            x = min(len(a),len(b))
            #从后往前枚举a和b的相同字符串，保证最长
            for i in range(x,-1,-1):
                if a[-i:] == b[:i]:
                    return a + b[i:]
            return a+b

        ans = []
        for a, b, c in permutations((a, b, c)):
            x = find(find(a, b), c)
            ans.append((len(x),x)
        ans.sort(key = lambda x:(x[0],x[1]))
        return ans[0][1]

雪景式

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minimumString(self, a: str, b: str, c: str) -> str:
        def merge(s1,s2):
            # 如果s2包含在s1里面那么就不需要拼在后面了
            if s2 in s1:
                return s1
            # 靠后缀拼起来
            for l in range(min(len(s1),len(s2)),0,-1):
                if s1[-l:] == s2[:l]:
                    return s1[:-l] + s2
            return s1 + s2
        abc = merge(merge(a,b),c)
        acb = merge(merge(a,c),b)
        bac = merge(merge(b,a),c)
        bca = merge(merge(b,c),a)
        cab = merge(merge(c,a),b)
        cba = merge(merge(c,b),a)
        # 返回长度最小再字典序最小
        return min([abc,acb,bac,bca,cab,cba],key=lambda x:(len(x),x))

精简

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def minimumString(self, a: str, b: str, c: str) -> str:
        from itertools import permutations
        def merge(s1,s2):
            if s2 in s1:
                return s1
            for l in range(min(len(s1),len(s2)),0,-1):
                if s1[-l:] == s2[:l]:
                    return s1[:-l] + s2
            return s1 + s2
        return min((merge(merge(x,y),z) for x,y,z in permutations([a,b,c],3)),key = lambda x:(len(x),x))

灵神

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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