| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
中等 |
1855 |
第 356 场周赛 Q3 |
|
给你三个字符串 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只包含小写英文字母。
我们枚举三个字符串的所有排列，然后对于每个排列，对三个字符串进行合并，找到最短的且字典序最小的字符串。
时间复杂度
class Solution:
def minimumString(self, a: str, b: str, c: str) -> str:
def f(s: str, t: str) -> str:
if s in t:
return t
if t in s:
return s
m, n = len(s), len(t)
for i in range(min(m, n), 0, -1):
if s[-i:] == t[:i]:
return s + t[i:]
return s + t
ans = ""
for a, b, c in permutations((a, b, c)):
s = f(f(a, b), c)
if ans == "" or len(s) < len(ans) or (len(s) == len(ans) and s < ans):
ans = s
return ansclass Solution {
public String minimumString(String a, String b, String c) {
String[] s = {a, b, c};
int[][] perm = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 1, 0}, {2, 0, 1}};
String ans = "";
for (var p : perm) {
int i = p[0], j = p[1], k = p[2];
String t = f(f(s[i], s[j]), s[k]);
if ("".equals(ans) || t.length() < ans.length()
|| (t.length() == ans.length() && t.compareTo(ans) < 0)) {
ans = t;
}
}
return ans;
}
private String f(String s, String t) {
if (s.contains(t)) {
return s;
}
if (t.contains(s)) {
return t;
}
int m = s.length(), n = t.length();
for (int i = Math.min(m, n); i > 0; --i) {
if (s.substring(m - i).equals(t.substring(0, i))) {
return s + t.substring(i);
}
}
return s + t;
}
}class Solution {
public:
string minimumString(string a, string b, string c) {
vector<string> s = {a, b, c};
vector<vector<int>> perm = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 1, 0}, {2, 0, 1}};
string ans = "";
for (auto& p : perm) {
int i = p[0], j = p[1], k = p[2];
string t = f(f(s[i], s[j]), s[k]);
if (ans == "" || t.size() < ans.size() || (t.size() == ans.size() && t < ans)) {
ans = t;
}
}
return ans;
}
string f(string s, string t) {
if (s.find(t) != string::npos) {
return s;
}
if (t.find(s) != string::npos) {
return t;
}
int m = s.size(), n = t.size();
for (int i = min(m, n); i; --i) {
if (s.substr(m - i) == t.substr(0, i)) {
return s + t.substr(i);
}
}
return s + t;
};
};func minimumString(a string, b string, c string) string {
f := func(s, t string) string {
if strings.Contains(s, t) {
return s
}
if strings.Contains(t, s) {
return t
}
m, n := len(s), len(t)
for i := min(m, n); i > 0; i-- {
if s[m-i:] == t[:i] {
return s + t[i:]
}
}
return s + t
}
s := [3]string{a, b, c}
ans := ""
for _, p := range [][]int{{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}} {
i, j, k := p[0], p[1], p[2]
t := f(f(s[i], s[j]), s[k])
if ans == "" || len(t) < len(ans) || (len(t) == len(ans) && t < ans) {
ans = t
}
}
return ans
}function minimumString(a: string, b: string, c: string): string {
const f = (s: string, t: string): string => {
if (s.includes(t)) {
return s;
}
if (t.includes(s)) {
return t;
}
const m = s.length;
const n = t.length;
for (let i = Math.min(m, n); i > 0; --i) {
if (s.slice(-i) === t.slice(0, i)) {
return s + t.slice(i);
}
}
return s + t;
};
const s: string[] = [a, b, c];
const perm: number[][] = [
[0, 1, 2],
[0, 2, 1],
[1, 0, 2],
[1, 2, 0],
[2, 0, 1],
[2, 1, 0],
];
let ans = '';
for (const [i, j, k] of perm) {
const t = f(f(s[i], s[j]), s[k]);
if (ans === '' || t.length < ans.length || (t.length === ans.length && t < ans)) {
ans = t;
}
}
return ans;
}impl Solution {
fn f(s1: String, s2: String) -> String {
if s1.contains(&s2) {
return s1;
}
if s2.contains(&s1) {
return s2;
}
for i in 0..s1.len() {
let s = &s1[i..];
if s2.starts_with(s) {
let n = s.len();
return s1 + &s2[n..];
}
}
s1 + s2.as_str()
}
pub fn minimum_string(a: String, b: String, c: String) -> String {
let s = [&a, &b, &c];
let perm = [
[0, 1, 2],
[0, 2, 1],
[1, 0, 2],
[1, 2, 0],
[2, 0, 1],
[2, 1, 0],
];
let mut ans = String::new();
for [i, j, k] in perm.iter() {
let r = Self::f(Self::f(s[*i].clone(), s[*j].clone()), s[*k].clone());
if ans == "" || r.len() < ans.len() || (r.len() == ans.len() && r < ans) {
ans = r;
}
}
ans
}
}我们可以使用 KMP 算法来优化字符串的合并过程。
时间复杂度
class Solution:
def minimumString(self, a: str, b: str, c: str) -> str:
def f(s: str, t: str) -> str:
if s in t:
return t
if t in s:
return s
p = t + "#" + s + "$"
n = len(p)
next = [0] * n
next[0] = -1
i, j = 2, 0
while i < n:
if p[i - 1] == p[j]:
j += 1
next[i] = j
i += 1
elif j:
j = next[j]
else:
next[i] = 0
i += 1
return s + t[next[-1] :]
ans = ""
for a, b, c in permutations((a, b, c)):
s = f(f(a, b), c)
if ans == "" or len(s) < len(ans) or (len(s) == len(ans) and s < ans):
ans = s
return ansclass Solution {
public String minimumString(String a, String b, String c) {
String[] s = {a, b, c};
int[][] perm = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 1, 0}, {2, 0, 1}};
String ans = "";
for (var p : perm) {
int i = p[0], j = p[1], k = p[2];
String t = f(f(s[i], s[j]), s[k]);
if ("".equals(ans) || t.length() < ans.length()
|| (t.length() == ans.length() && t.compareTo(ans) < 0)) {
ans = t;
}
}
return ans;
}
private String f(String s, String t) {
if (s.contains(t)) {
return s;
}
if (t.contains(s)) {
return t;
}
char[] p = (t + "#" + s + "$").toCharArray();
int n = p.length;
int[] next = new int[n];
next[0] = -1;
for (int i = 2, j = 0; i < n;) {
if (p[i - 1] == p[j]) {
next[i++] = ++j;
} else if (j > 0) {
j = next[j];
} else {
next[i++] = 0;
}
}
return s + t.substring(next[n - 1]);
}
}class Solution {
public:
string minimumString(string a, string b, string c) {
vector<string> s = {a, b, c};
vector<vector<int>> perm = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 1, 0}, {2, 0, 1}};
string ans = "";
for (auto& p : perm) {
int i = p[0], j = p[1], k = p[2];
string t = f(f(s[i], s[j]), s[k]);
if (ans == "" || t.size() < ans.size() || (t.size() == ans.size() && t < ans)) {
ans = t;
}
}
return ans;
}
string f(string s, string t) {
if (s.find(t) != string::npos) {
return s;
}
if (t.find(s) != string::npos) {
return t;
}
string p = t + "#" + s + "$";
int n = p.size();
int next[n];
next[0] = -1;
next[1] = 0;
for (int i = 2, j = 0; i < n;) {
if (p[i - 1] == p[j]) {
next[i++] = ++j;
} else if (j > 0) {
j = next[j];
} else {
next[i++] = 0;
}
}
return s + t.substr(next[n - 1]);
};
};func minimumString(a string, b string, c string) string {
f := func(s, t string) string {
if strings.Contains(s, t) {
return s
}
if strings.Contains(t, s) {
return t
}
p := t + "#" + s + "$"
n := len(p)
next := make([]int, n)
next[0] = -1
for i, j := 2, 0; i < n; {
if p[i-1] == p[j] {
j++
next[i] = j
i++
} else if j > 0 {
j = next[j]
} else {
next[i] = 0
i++
}
}
return s + t[next[n-1]:]
}
s := [3]string{a, b, c}
ans := ""
for _, p := range [][]int{{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}} {
i, j, k := p[0], p[1], p[2]
t := f(f(s[i], s[j]), s[k])
if ans == "" || len(t) < len(ans) || (len(t) == len(ans) && t < ans) {
ans = t
}
}
return ans
}function minimumString(a: string, b: string, c: string): string {
const f = (s: string, t: string): string => {
if (s.includes(t)) {
return s;
}
if (t.includes(s)) {
return t;
}
const p = t + '#' + s + '$';
const n = p.length;
const next: number[] = Array(n).fill(0);
next[0] = -1;
for (let i = 2, j = 0; i < n; ) {
if (p[i - 1] === p[j]) {
next[i++] = ++j;
} else if (j) {
j = next[j];
} else {
next[i++] = 0;
}
}
return s + t.slice(next[n - 1]);
};
const s: string[] = [a, b, c];
const perm: number[][] = [
[0, 1, 2],
[0, 2, 1],
[1, 0, 2],
[1, 2, 0],
[2, 0, 1],
[2, 1, 0],
];
let ans = '';
for (const [i, j, k] of perm) {
const t = f(f(s[i], s[j]), s[k]);
if (ans === '' || t.length < ans.length || (t.length === ans.length && t < ans)) {
ans = t;
}
}
return ans;
}