# 8ms C++ Solution

• ``````class Solution {
public:
string alienOrder(vector<string>& words)
{
if (words.size() ==0) return "";

unordered_map<char, int> ingress;

for (auto& w : words)
{
for (auto& ch : w)
{
ingress[ch];
}
}

vector<pair<char, char>> pairs;
for (int i = 0; i < words.size() - 1; i++)
{
pair<char, char> p;
if (scan(words[i], words[i + 1], p))
{
pairs.push_back(p);
}
}

for (auto& p : pairs)
{
if (ingress.find(p.second) == ingress.end()) ingress[p.second] = 1;
else ingress[p.second]++;
}

stack<char> stack;
for (unordered_map<char, int>::iterator iter = ingress.begin(); iter != ingress.end(); iter++)
{
if (iter->second == 0) stack.push(iter->first);
}

if (stack.size() == 0 && stack.size() > 1) return "";

string ret;
while (stack.size() > 0)
{
char top = stack.top();
stack.pop();
ret += top;

for (auto& p : pairs)
{
if (p.first == top)
{
ingress[p.second]--;
if (ingress[p.second] == 0) stack.push(p.second);
}
}
}

for (unordered_map<char, int>::iterator iter = ingress.begin(); iter != ingress.end(); iter++)
{
if (iter->second != 0) return "";
}

return ret;
}

bool scan(string w1, string w2, pair<char, char>& p)
{
int k = 0;
while (k < w1.size() && k < w2.size() && w1[k] == w2[k]) k++;
if (k < w1.size() && k < w2.size())
{
p.first = w1[k];
p.second = w2[k];
return true;
}

return false;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.