【CheckiO】Determine the order


这题显然是个拓扑排序

不过用Python写拓扑排序实在是太麻烦了

后来看了一下高手的解法

#!/usr/bin/env python2

def checkio(data):
    distinct_letters = sorted(set("".join(data)))
    print distinct_letters
    #We just get couples of letters (a, b) such that a must be before b
    constraints = [(word[i], word[i + 1]) for word in data for i in range(len(word) - 1)]
    
    solution_found = False
    while not solution_found:
        solution_found = True
        for (a, b) in constraints:
            ia = distinct_letters.index(a)
            ib = distinct_letters.index(b)
            if ia > ib:
                #We swap the letters
                distinct_letters[ia] = b
                distinct_letters[ib] = a
                solution_found = False
    return "".join(distinct_letters)

发现自己的思路太僵化了

这毕竟不是ACM的题目

没有时间复杂度的限制

解决问题的时候完全可以采取一些时间复杂度高但容易实现的解法