LeetCode solutions | MaskRay

LeetCode solutions | MaskRay

You have solved 426/429 problems. 主要追求兩個目標：代碼簡短，時間空間複雜度低。

註記

4-sum

使用了multimap，時間複雜度$O(n^2\log{n})$，得到所有答案後不需要去重操作。

合法的四元組有三類：

• a<=b<c<=d，枚舉c和d，判斷是否存在和爲target-c-d的二元組
• a<=b=c<=d，枚舉b和d，判斷是否存在target-b-b-d
• a=b=c<=d，枚舉a，判斷是否存在target-a-a-a

分別統計，小心實現可以保證不會產生相同的候選解，從而無需去重。

Alien Dictionary

對於每一對單詞，可以確定去除最長公共前綴後的下一對字母的大小關係。兩個單詞的最長公共前綴等於夾在其中的(所有相鄰單詞對的最長公共前綴)的最小值。根據相鄰單詞對的信息即可推得所有任意單詞對的信息。因此只需根據相鄰單詞對求出拓撲關係。

Read full article from LeetCode solutions | MaskRay