Description#
Given three strings a, b, and c, your task is to find a string that has the minimum length and contains all three strings as substrings.
If there are multiple such strings, return the lexicographically smallest one.
Return a string denoting the answer to the problem.
Notes
- A string
a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. - A substring is a contiguous sequence of characters within a string.
Example 1:
Input: a = "abc", b = "bca", c = "aaa"
Output: "aaabca"
Explanation: We show that "aaabca" contains all the given strings: a = ans[2...4], b = ans[3..5], c = ans[0..2]. It can be shown that the length of the resulting string would be at least 6 and "aaabca" is the lexicographically smallest one.
Example 2:
Input: a = "ab", b = "ba", c = "aba"
Output: "aba"
Explanation: We show that the string "aba" contains all the given strings: a = ans[0..1], b = ans[1..2], c = ans[0..2]. Since the length of c is 3, the length of the resulting string would be at least 3. It can be shown that "aba" is the lexicographically smallest one.
Constraints:
1 <= a.length, b.length, c.length <= 100a, b, c consist only of lowercase English letters.
Solutions#
Solution 1: Enumeration#
We enumerate all permutations of the three strings, and for each permutation, we merge the three strings to find the shortest string with the smallest lexicographical order.
The time complexity is $O(n^2)$, and the space complexity is $O(n)$. Where $n$ is the maximum length of the three strings.
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 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 ans
|
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
| class 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;
}
}
|
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
| 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;
};
};
|
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
| 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
}
|
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
| 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;
}
|
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
| 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
}
}
|
