# 16/18 lines Python, 30 lines C++

• Two similar solutions. Both first go through the word list to find letter pairs `(a, b)` where `a` must come before `b` in the alien alphabet. The first solution just works with these pairs, the second is a bit smarter and uses successor/predecessor sets. Doesn't make a big difference here, though, I got both accepted in 48 ms.

Solution 1

``````def alienOrder(self, words):
less = []
for pair in zip(words, words[1:]):
for a, b in zip(*pair):
if a != b:
less += a + b,
break
chars = set(''.join(words))
order = []
while less:
free = chars - set(zip(*less)[1])
if not free:
return ''
order += free
less = filter(free.isdisjoint, less)
chars -= free
return ''.join(order + list(chars))
``````

Solution 2

``````def alienOrder(self, words):
pre, suc = collections.defaultdict(set), collections.defaultdict(set)
for pair in zip(words, words[1:]):
for a, b in zip(*pair):
if a != b:
break
chars = set(''.join(words))
free = chars - set(pre)
order = ''
while free:
a = free.pop()
order += a
for b in suc[a]:
if not pre[b]:
return order * (set(order) == chars)
``````

C++ version of solution 2

``````string alienOrder(vector<string>& words) {
map<char, set<char>> suc, pre;
set<char> chars;
string s;
for (string t : words) {
chars.insert(t.begin(), t.end());
for (int i=0; i<min(s.size(), t.size()); ++i) {
char a = s[i], b = t[i];
if (a != b) {
suc[a].insert(b);
pre[b].insert(a);
break;
}
}
s = t;
}
set<char> free = chars;
for (auto p : pre)
free.erase(p.first);
string order;
while (free.size()) {
char a = *begin(free);
free.erase(a);
order += a;
for (char b : suc[a]) {
pre[b].erase(a);
if (pre[b].empty())
free.insert(b);
}
}
return order.size() == chars.size() ? order : "";
}``````

• Hi, Stefan. I think you are actually using BFS in your solutions (`pre` is actually to record the indegrees of the nodes), right? Well, your implementation is really clever.

BTW, a little question, why do you design `order` to be a list instead of a string in the Python solutions?

• Maybe it's BFS, though since it's not quite the usual BFS, I'm reluctant to call it that.
Yes, `pre` is in-degrees. Maybe not a good name.

In my first solution, which can add multiple free characters at once, I made `order` a list to avoid needing another `''.join(...)` there. In the second solution, it was just stupid and I changed it to string now. Thanks.

• Nice code. The BFS toposort is implemented in a very clean and concise manner.

• Quite elegant solution !

• This post is deleted!

• So many of your code samples are the best solutions I've seen. Thank you!

• Hi, Stefan, I found your C++ solution can't pass the oJ now. For the input ["za","zb","ca","cb"], the a->b dependency will be calculated twice then lead the b to have in-degree 2. Then the output will be wrong.
I think for the pre container, will should change it to be map<char, set<char>> instead of map<char, int> to avoid the redundancy.
B.T.W., why you don't use unordered_map and unordered_set? I think they may be faster.

• Most of the answers here check only difference between " adjacent words". But what if the input is ("abc", "ac", "acd"), will it miss the case where d should be after c?

• @junhuangli What do you mean with "miss the case"?

• nvm, my counter case is invalid, there is no such a case, adjacent comparing is enough.

• Nice solutions! But as @li61 said, looks like your second Python solution failed on ["za","zb","ca","cb"] ?
I guess OJ updated the test cases after you posted your code ^_^

• Here is my python code inspired by yours, although BFS topological sort wasn't in your mind when you came up with this solution, but it's actually a BFS topological sort :)

In my code I just made everything behave more like a BFS, and fixed your bug that failed on ["za","zb","ca","cb"].

``````def alienOrder(self, words):
chars = set("".join(words))
degrees = {x:0 for x in chars}
graph = collections.defaultdict(list)
for pair in zip(words, words[1:]):
for x, y in zip(*pair):
if x != y:
graph[x].append(y)
degrees[y] += 1
break

queue = filter(lambda x: degrees[x] == 0, degrees.keys())
ret = ""
while queue:
x = queue.pop()
ret += x
for n in graph[x]:
degrees[n] -= 1
if degrees[n] == 0:
queue.append(n)

return ret * (set(ret) == chars)``````

• @li61 Thanks, I fixed it now (missed your comment earlier). I did change `pre` to `map<char, set>` like you said, though changing `suc` to `map<char, multisetset>` would've worked as well (and in that case, no other changes would've been necessary). Why I don't use the `unordered_` versions? I guess I just don't like the long names, so I might use the short ones unless I have a good reason not to. Since there are only up to 26 keys here, I don't think it would really make a difference.

@chris.zhang.336 Thanks for pointing it out again. Yes, must have been added later. The solution had been accepted earlier.

• Nah, mine is really something random somewhat between DFS and BFS. And I'd say yours isn't more like BFS but more like DFS. Calling your stack "queue" doesn't make it one :-)

• maybe use pop(0) would make it looks more like a queue :-)

• +1 chris. Made it very easy to understand

• Your python code is very neat, use a lot of syntax sugar such as zip, unzip.

• May I ask what and why for these two lines? Thanks
for (auto p : pre)
free.erase(p.first);

• @coder2 `free` is the set of free-to-use chars, which I initialize as being all chars and then erase all non-free ones.

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