友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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只包含小写英文字母。
思路分析
先使用回溯获取三个字符串的所有全排列，然后在这些全排列中，通过合并字符串首尾相同的部分来获取更短的子串，在这些子串中选择最短，字典排序最小的字符串。
| 合并字符串时，注意处理首尾的相同子串。 |
最初思路是直接合并三个字符，这样会因为没有处理“首尾相同”的子串而让结果变长。
-
一刷
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-05 22:38:45
*/
public String minimumString(String a, String b, String c) {
List<List<String>> perms = new ArrayList<>(6);
List<String> ss = Arrays.asList(a, b, c);
backtrack(ss, perms, new ArrayList<>(), new boolean[ss.size()]);
String result = null;
for (List<String> perm : perms) {
String temp = merge(merge(perm.get(0), perm.get(1)), perm.get(2));
if (result == null || temp.length() < result.length()
|| temp.length() == result.length() && temp.compareTo(result) < 0) {
result = temp;
}
}
return result;
}
private String merge(String a, String b) {
if (a.contains(b)) return a;
if (b.contains(a)) return b;
int min = Math.min(a.length(), b.length());
for (int i = min; i > 0; i--) {
// 如果 a 的结尾和 b 的开头子串相同，则该子串只需要出现一次
if (a.substring(a.length() - i)
.equals(b.substring(0, i))) {
return a + b.substring(i);
}
}
return a + b;
}
private void backtrack(List<String> ss, List<List<String>> set,
List<String> path, boolean[] used) {
if (ss.size() == path.size()) {
set.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < ss.size(); i++) {
if (used[i]) {
continue;
}
used[i] = true;
path.add(ss.get(i));
backtrack(ss, set, path, used);
path.removeLast();
used[i] = false;
}
}