Involving knowledge points
Sorted set string
Title
You are given three strings a, b and c. Your task is to find the string with the shortest length, and these three strings are all its substrings.
If there are multiple such strings, please return the one with the smallest lexicographic order.
Please return a string that meets the question requirements.
Notice:
Two strings a and b are of the same length. If the letter of a is earlier in the alphabet than the letter of b at the first different character, then string a is lexicographically smaller than string b.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: a = “abc”, b = “bca”, c = “aaa”
Output: “aaabca”
Explanation: The string “aaabca” contains all three strings: a = ans[2…4], b = ans[3…5], c = ans[0…2]. The length of the resulting string is at least 6, and “aaabca” is the lexicographically smallest one.
Example 2:
Input: a = “ab”, b = “ba”, c = “aba”
Output: “aba”
Explanation: The string “aba” contains all three 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 is at least 3 . “aba” is the lexicographically smallest one.
Parameter range:
1 <= a.length, b.length, c.length <= 100
a, b, c only contain lowercase English letters.
Analysis
Merge two strings
Assume a is in front and b is in back. There are two situations as follows.
| a includes b | a=”ab”, b=”a”, after merging, it is “ab” |
| The suffix of a is the same as the prefix of b, hereafter referred to as the common post-prefix | a=”ab”,b=”bc”, after merging”abc” |
Divided into two parts
| First step | Second step |
|---|---|
| ab | abc |
| ab | c(ab) |
| ac | acb |
| ac | b(ac) |
| ba | bac |
| ba | c(ba) |
| bc | bca |
| bc | a(bc) |
| ca | cab |
| ca | b(ca) |
| cb | cba |
| cb | a(cb) |
| A total of 12 situations |
abc is the same as a(bc)
Compared with a(bc), abc has the same or better effect, so there is no need to consider a(bc), etc.
| bc is the first case | abc is ab, and so is a(bc) |
| ab is the first case | This case is not consistent, abc=ac a(bc) is equal to a(xc). If the prefix of xc is the suffix of a and is longer than x, then c is also a suffix, and the length saved by the two is the same. If the prefix of xc is not the suffix of a, the prefix of c may be the suffix of a. In this case: abcis better thana(bc). |
| ab and bc are both the second case | abc = a minus ab common postfix + b + c minus bc common postfix a (bc) also |
Explanation of variable functions
| m_setStrs | Record backup Select the answer, automatically sort according to length and lexicographic order |
| next_permutation | Next order, initially sorted, so that the initial minimum order |
Code
class Solution {<!-- -->
public:
string minimumString(string a, string b, string c) {<!-- -->
vector<string> strs = {<!-- --> a,b,c };
sort(strs.begin(), strs.end());
do
{<!-- -->
string tmp = Union(strs[0], strs[1]);
tmp = Union(tmp, strs[2]);
m_setStrs.emplace(tmp.length(), tmp);
} while (next_permutation(strs.begin(), strs.end()));
return m_setStrs.begin()->second;
}
string Union(const string & amp; a, const string & amp; b)
{<!-- -->
if (-1 != a.find(b))
{<!-- -->
return a;
}
int len = min(a.length(), b.length());
int i = len;
for (; i > 0; i--)
{<!-- -->
if (a.substr(a.length() - i) == b.substr(0, i))
{<!-- -->
break;
}
}
return a.substr(0, a.length() - i) + b;
}
std::set<std::pair<int, string>> m_setStrs;
};
Legacy code
class Solution {
public:
string minimumString(string a, string b, string c) {
vector strs = { a,b,c };
sort(strs.begin(), strs.end());
if (-1 != strs[1].find(strs[0]))
{
strs[0] = “”;
}
if (-1 != strs[2].find(strs[1]))
{
strs[1] = “”;
}
do
{
Union(strs[0], strs[1], strs[2]);
} while (next_permutation(strs.begin(), strs.end()));
return m_setStrs.begin()->second;
}
void Union(const string & amp; a, const string & amp; b, const string & amp; c)
{
string tmp = Union(a, b);
tmp = Union(tmp, c);
m_setStrs.emplace(tmp.length(), tmp);
}
string Union(const string & amp; a, const string & amp; b)
{
if (-1 != a.find(b))
{
return a;
}
int len = min(a.length(), b.length());
int i = len;
for (; i > 0; i–)
{
if (a.substr(a.length()-i)== b.substr(0,i))
{
break;
}
}
return a.substr(0, a.length() – i) + b;
}
std::set
};
Old version code 2
class Solution {
public:
string minimumString(string a, string b, string c) {
Union(a, b, c);
Union(a, c, b);
Union(b, a, c);
Union(b, c, a);
Union(c, a, b);
Union(c, b, a);
return m_setStrs.begin()->second;
}
void Union(const string & amp; a, const string & amp; b, const string & amp; c)
{
string tmp = Union(a, b);
tmp = Union(tmp, c);
m_setStrs.emplace(tmp.length(),tmp);
tmp = Union(b, c);
tmp = Union(a, tmp);
m_setStrs.emplace(tmp.length(), tmp);
}
string Union(const string & amp; a, const string & amp; b)
{
if (-1 != a.find(b))
{
return a;
}
int len = min(a.length(), b.length());
int i = len;
for (; i > 0; i–)
{
if (Same(a, b, i))
{
break;
}
}
return a.substr(0, a.length() – i) + b;
}
bool Same(const string & amp; a, const string & amp; b, int len)
{
for (int i = 0; i < len; i + + )
{
if (a[a.length() – len + i] != b[i])
{
return false;
}
}
return true;
}
std::set
};
August 2023 code
class Solution {
public:
string minimumString(string a, string b, string c) {
Cat(a, b, c);
Cat(a, c, b);
Cat(b, a, c);
Cat(b, c, a);
Cat(c, a, b);
Cat(c, b, a);
string strRet = *m_setCan.begin();
for (const auto & amp; it : m_setCan )
{
if (it.length() < strRet.length())
{
strRet = it;
}
}
return strRet;
}
void Cat(string a, string b, string c)
{
std::set setCan;
Cat(setCan, a, b);
for (const auto & amp; it : setCan)
{
Cat(m_setCan, it, c);
}
}
void Cat(std::set & amp; setCan,string a, string b)
{
int i = min(a.length(), b.length());
for (; i >= 1 ; i–)
{
const auto tmp1 = a.substr(a.length() – i);
const auto tmp2 = b.substr(0, i);
if (tmp1 == tmp2)
{
setCan.emplace(a + b.substr(i));
}
}
setCan.emplace(a + b);
if (-1 != a.find(b))
{
setCan.emplace(a);
}
}
std::set m_setCan;
};
Extended reading
Video course
Effective learning: clear goals, timely feedback, stretching zone (appropriate difficulty), you can learn simple courses first, please go to CSDN Academy and listen to the explanation of Baiyin Lecturer (that is, I).
https://edu.csdn.net/course/detail/38771
how fast do you want
A battle has quickly formed. To share the worries of your boss, please learn C# onboarding training, C++ onboarding training and other courses.
https://edu.csdn.net/lecturer/6176
Related downloads
If you want to know the superior learning algorithm, please download the doc version of “Algorithm Book When You Hear the Defects”
https://download.csdn.net/download/he_zhidan/88348653
| What the Sa family wants to say to everyone |
|---|
| It is a good wish to be happy when you hear the flaws. Discover problems and correct them early to save your boss money. |
| The origin of the Mohist name: everything is recorded in Mohism. |
| If the program is a one-stop process, then the algorithm is its key point |
Test environment
Operating system: win7 Development environment: VS2019 C++ 17
Or operating system: win10 development environment:
VS2022 C++ 17
