FourStrings
SRM 677 · 2015-11-03 · by cgy4ever
SRM 677 · 2015-11-03 · by cgy4ever · String Manipulation
Problem Statement
Problem Statement
We have four String s: a, b, c, and d.
A superstring of our four strings is any string S such that each of the four strings occurs somewhere in S as a contiguous substring. Note that some superstrings of our four strings always exist.
For example, the string S = a+b+c+d is obviously a superstring of a, b, c, and d.
Find and return the length of the shortest superstring of a, b, c, and d.
A superstring of our four strings is any string S such that each of the four strings occurs somewhere in S as a contiguous substring. Note that some superstrings of our four strings always exist.
For example, the string S = a+b+c+d is obviously a superstring of a, b, c, and d.
Find and return the length of the shortest superstring of a, b, c, and d.
Constraints
- a will contain between 1 and 10 characters, inclusive.
- b will contain between 1 and 10 characters, inclusive.
- c will contain between 1 and 10 characters, inclusive.
- d will contain between 1 and 10 characters, inclusive.
- Each character in a will be a lowercase English letter ('a'-'z').
- Each character in b will be a lowercase English letter ('a'-'z').
- Each character in c will be a lowercase English letter ('a'-'z').
- Each character in d will be a lowercase English letter ('a'-'z').
Examples
0)
"abc" "ab" "bc" "b" Returns: 3
The shortest superstring in this test case is the string "abc". Note that each of the other three strings occurs in "abc" as a contiguous substring.
1)
"a" "bc" "def" "ghij" Returns: 10
In this case, one possible shortest superstring is "abcdefghij".
2)
"top" "coder" "opco" "pcode" Returns: 8
S = "topcoder"
3)
"thereare" "arelots" "lotsof" "ofcases" Returns: 19
4)
"aba" "b" "b" "b" Returns: 3
Submissions are judged against all 74 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FourStrings with a public method int shortestLength(string a, string b, string c, string d) · 74 test cases · 2 s / 256 MB per case