m***o 发帖数: 1738 | 1 大牛们给个思路,前段时间另一道题的逆转。
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 | f***b 发帖数: 21 | 2 给字符串数组建图,然后求拓扑排序,返回排序结果即可 | m***o 发帖数: 1738 | 3 谢谢大牛,再问一下这个题的 sample code。
【在 f***b 的大作中提到】 : 给字符串数组建图,然后求拓扑排序,返回排序结果即可
| r****7 发帖数: 2282 | 4 首先这个结果不唯一,而且可能性很多,只能取一个
按位比较然后得到一个字符的有向图然后拓扑排序吧
【在 m***o 的大作中提到】 : 大牛们给个思路,前段时间另一道题的逆转。 : 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
| m*****k 发帖数: 731 | | f**********t 发帖数: 1001 | 6 // 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);
} |
|