不难的一道题，就是根据单词列表的顺序，找两两单词间第一对不一样的字母，构建一个有向图，然后拓扑排序一下，代码：
class Solution {
public:
string alienOrder(vector<string>& words) {
string result;
if (words.size() >= 2){
vector<pair<string, string>> order_nodes;
vector<pair<string, string>> tmp;
for (int i = 0; i < words.size() - 1; ++i) {
stringstream ss;
ss << words[i];
string a = ss.str();
ss.str("");
ss << words[i + 1];
string b = ss.str();
ss.str("");
tmp = searchFirstDiff(a, b);
for (int n = 0; n < tmp.size(); ++n)
order_nodes.push_back(tmp[n]);
}
map<string, int> letter_map = generateLetterMap(order_nodes);
cout << "finish generating letter map" << endl;
vector<vector<int>> map_matrix(letter_map.size(), vector<int>(letter_map.size(), 0));
for (int i = 0; i < order_nodes.size(); ++i) {
if (order_nodes[i].first != order_nodes[i].second)
map_matrix[letter_map[order_nodes[i].first]][letter_map[order_nodes[i].second]] = 1;
}
map<string, int> letter_in = generateLetterIn(map_matrix, letter_map);
vector<string> stack;
for (map<string, int>::iterator iter = letter_in.begin(); iter != letter_in.end(); ++iter) {
if (iter->second == 0)
stack.push_back(iter->first);
}
cout << "prepare for stack process" << endl;
while (stack.size() != 0) {
for (int i = 0; i < stack.size(); ++i) {
cout << "enter loop" << endl;
result.append(stack[i]);
--letter_in[stack[i]];
for (map<string, int>::iterator iter = letter_map.begin(); iter != letter_map.end(); ++iter) {
cout << "enter sub loop" << endl;
letter_in[iter->first] -= map_matrix[letter_map[stack[i]]][iter->second];
}
}
stack.clear();
for (map<string, int>::iterator iter = letter_in.begin(); iter != letter_in.end(); ++iter) {
if (iter->second == 0)
stack.push_back(iter->first);
}
}
}
return result;
}
vector<pair<string, string>> searchFirstDiff(const string& a, const string& b) {
cout << "origin string: " << a << " " << b << endl;
int cmp_length = min(a.length(), b.length());
cout << "cmp_length: " << cmp_length << endl;
vector<pair<string, string>> result;
for (int i = 0; i < cmp_length; ++i) {
if (a[i] == b[i]) {
cout << a[i] << " " << b[i] << endl;
stringstream ss;
ss << a[i];
string result_a = ss.str();
ss.str("");
ss << b[i];
string result_b = ss.str();
ss.str("");
cout << "first diff: " << result_a << " " << result_b << endl;
result.push_back(pair<string, string>(result_a, result_b));
}
else
{
cout << "enter cmp" << endl;
stringstream ss;
ss << a[i];
string result_a = ss.str();
ss.str("");
ss << b[i];
string result_b = ss.str();
ss.str("");
cout << "first diff: " << result_a << " " << result_b << endl;
result.push_back(pair<string, string>(result_a, result_b));
}
}
return result;
}
map<string, int> generateLetterMap(const vector<pair<string, string>>& tmp) {
//cout << "enter generate letter map" << endl;
map<string, int> letter_map;
int index = 0;
for (int i = 0; i < tmp.size(); ++i) {
//cout << "enter for loop" << endl;
pair<map<string, int>::iterator, bool> insert_result;
insert_result = letter_map.insert(pair<string, int>(tmp[i].first, index));
if (insert_result.second)
++index;
insert_result = letter_map.insert(pair<string, int>(tmp[i].second, index));
if (insert_result.second)
++index;
}
return letter_map;
}
map<string, int> generateLetterIn(const vector<vector<int>>& map_matrix, map<string, int>& letter_map) {
//cout << "enter generating letter in" << endl;
map<string, int> letter_in;
map<string, int>::iterator iter;
for (iter = letter_map.begin(); iter != letter_map.end(); ++iter) {
//cout << "enter looping" << endl;
int in_number = 0;
for (int j = 0; j < letter_map.size(); ++j) {
in_number += map_matrix[j][iter->second];
}
letter_in.insert(pair<string, int>(iter->first, in_number));
}
return letter_in;
}
};
结果这个用例没有过，一看就是用例有问题，这个用例里，c的前驱后驱显然是无法确定的，测了其他几个用例都是对的，就没管了。
