Non-Leetcode Questions: Derive Order for New Language
here's a new language which uses the latin alphabet. However, you don't know the order among letters.It could be:
a b c d ...
as it could also be:
b e z a m i ...
You receive a list of words lexicographically sorted by the rules of this new language. From this list, derive one valid particular ordering of letters in this language.
Naive Thinking: 这道题是我从来没有见过的类型，想了半天还是想不出来，看了答案，原来是拓扑排序。好厉害呀。
算法复杂度是O(nk) k是平均每个单词的长。从index = 0开始，每次都先找到前一个字母一样的[begin, end]区段，然后调用子函数setOrder(Node[] order, String[] strs, int begin, int end, int index)去连接对应节点，这一部分完成后就得到一个DAG，在DAG上运行拓扑排序得到的顺序就是新语言的顺序。
Read full article from Non-Leetcode Questions: Derive Order for New Language
No comments:
Post a Comment