// Given an string array sorted by characters in another string.
// Return that sorting base string.
// Example. give you
// {foo, cat, cao, bag, bat, aac}
// return: fcbagto
void buildGraph(vector &vs, unsigned col, unsigned up, unsigned down,
map> &res) {
char pre = '#';
unsigned count = 0;
unsigned uu = up;
for (unsigned i = up; i < down; ++i) {
if (vs[i].size() <= col) {
break;
}
if (vs[i][col] == pre) {
++count;
} else {
if (count > 1) {
buildGraph(vs, col + 1, uu, i, res);
}
if (pre != '#') {
res[pre].insert(vs[i][col]);
}
pre = vs[i][col];
count = 1;
uu = i;
}
}
if (count > 1) {
buildGraph(vs, col + 1, uu, down, res);
}
}
map> revert(const map> &mp) {
map> res;
for (auto item : mp) {
for (char c : item.second) {
res[c].insert(item.first);
}
if (res.find(item.first) == res.end()) {
res[item.first] = set();
}
}
return res;
}
void topoErase(map> &mp, map> &re,
char c, vector &res) {
res.push_back(c);
re.erase(re.find(c));
for (char child : mp[c]) {
re[child].erase(c);
if (re[child].empty()) {
topoErase(mp, re, child, res);
}
}
mp.erase(mp.find(c));
}
string topoSort(map> &mp) {
map> re = revert(mp);
vector vc;
while (!re.empty()) {
for (auto item : re) {
if (item.second.empty()) {
topoErase(mp, re, item.first, vc);
break;
}
}
}
return string(vc.begin(), vc.end());
}
string charOrder(vector &vs) {
map> mp;
buildGraph(vs, 0, 0, vs.size(), mp);
return topoSort(mp);
}
