16/18 lines Python, 30 lines C++


  • 51

    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:
                    suc[a].add(b)
                    pre[b].add(a)
                    break
        chars = set(''.join(words))
        free = chars - set(pre)
        order = ''
        while free:
            a = free.pop()
            order += a
            for b in suc[a]:
                pre[b].discard(a)
                if not pre[b]:
                    free.add(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 : "";
    }

  • 0

    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?


  • 0

    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.


  • 0
    S

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


  • 0
    J

    Quite elegant solution !


  • 0
    H
    This post is deleted!

  • 0
    E

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


  • 1
    L

    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.


  • 0
    J

    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?


  • 0

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


  • 0
    J

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


  • 0
    C

    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 ^_^


  • 13
    C

    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)

  • 0

    @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.


  • 1

    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 :-)


  • 0
    M

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


  • 0
    S

    +1 chris. Made it very easy to understand


  • 0
    5

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


  • 0
    C

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


  • 0

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


Log in to reply
 

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