NetworkXMessageRecovery
SRM 516 · 2011-05-25 · by dolphinigle
SRM 516 · 2011-05-25 · by dolphinigle · Greedy
Problem Statement
Problem Statement
Networks are infamous for being unreliable. Data sent over the network may be lost midway or received out of order. For the purpose of this problem, however, we will assume that the data will be received in the correct order but some parts of it may be missing.
The original message is a string consisting of distinct letters (lowercase and uppercase letters are considered distinct). This message is sent multiple times, and the received messages are given in theString[] messages. Each element of messages will be a subsequence (not necessarily contiguous) of the original message that retains the relative ordering between letters.
Your job is to return the shortest possible original message. The constraints will guarantee that at least one such message exists. If there are multiple such messages, return the lexicographically first one.
The original message is a string consisting of distinct letters (lowercase and uppercase letters are considered distinct). This message is sent multiple times, and the received messages are given in the
Your job is to return the shortest possible original message. The constraints will guarantee that at least one such message exists. If there are multiple such messages, return the lexicographically first one.
Notes
- The length of the answer for some cases may exceed 50 characters.
- If two Strings A and B have the same length, then A comes before B lexicographically if it has a smaller character at the first position where the Strings differ. When comparing the characters, refer to the following list of characters in ascending order: 'A', 'B', ..., 'Z', 'a', 'b', ..., 'z'.
Constraints
- messages will contain between 1 and 50 elements, inclusive.
- Each element of messages will contain between 1 and 50 characters, inclusive.
- messages will contain only the characters 'a'-'z' and 'A'-'Z'.
- For each i, all characters in messages[i] will be distinct.
- There will exist at least one string such that each element of messages is a subsequence of this string.
Examples
0)
{"acd", "bce"}
Returns: "abcde"
The only possible original strings of length 5 are: "abcde" "abced" "bacde" "baced" The lexicographically smallest of them is "abcde".
1)
{"ed", "dc", "cb", "ba"}
Returns: "edcba"
2)
{"Fox", "Ciel", "FoxCiel"}
Returns: "FoxCiel"
3)
{"a", "A"}
Returns: "Aa"
4)
{"a"}
Returns: "a"
Submissions are judged against all 122 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class NetworkXMessageRecovery with a public method string recover(vector<string> messages) · 122 test cases · 2 s / 256 MB per case