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 the String[] 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.
Tutorial
Code
class NetworkXMessageRecovery {
public:
string recover(vector<string> messages) {
int charset[300], sz;
memset(charset, 0, sizeof(charset));
sz = messages.size();
set<char> flag[300];
for (int i = 0; i < sz; i++) {
charset[messages[i][0]] = 1;
for (int j = 1; j < messages[i].size(); j++) {
char parent, child;
parent = messages[i][j - 1], child = messages[i][j];
flag[child].insert(parent);
charset[child] = 1;
}
}
string res = "";
for (int step = 0; step < 60; step++) {
vector<char> ans;
for (int i = 'A'; i <= 'Z'; i++)
if (charset[i] && !flag[i].size()) {
charset[i] = 0;
res += char(i);
ans.push_back(char(i));
break;
}
int sz = ans.size();
for (int i = 'a'; i <= 'z' && !sz; i++)
if (charset[i] && !flag[i].size()) {
charset[i] = 0;
res += char(i);
ans.push_back(char(i));
break;
}
for (int i = 0; i < ans.size(); i++) {
for (int j = 'A'; j <= 'Z'; j++)
flag[j].erase(ans[i]);
for (int j = 'a'; j <= 'z'; j++)
flag[j].erase(ans[i]);
}
}
return res;
}
}