給定一個僅包含小寫字母的英文單詞表，其中每個單詞最多包含50個字母。如果一張由一個詞或多個詞組成的表中，每個單詞（除了最后一個）都是排在它后面的單詞的前綴，則稱此表為一個詞鏈。例如下面的單詞組成了一個詞鏈：

i

int

integer

而下面的單詞不組成詞鏈：

integer

intern

    請在給定的單詞表中取出一些詞，組成最長的詞鏈。最長的詞鏈就是包含單詞數(shù)最多的詞鏈。

數(shù)據(jù)保證給定的單詞表中，單詞互不相同，并且單詞按字典順序排列。單詞數(shù)最多10000。

先給出解題報告上的思路：

用一個棧存儲當前的以第i個單詞結(jié)尾的最長詞鏈，第i+1個單詞加在棧的結(jié)尾（通過出棧保持棧所存儲的是一個詞鏈）。

    例如：

    i            棧 ： i

    int          棧：  i int

    integer      棧：  i int interger

    intern       棧：  i int intern （interger出棧）

    internet     棧：  i int intern internet

    可以證明，在第i個單詞插入后，當前在棧中的詞鏈就是包含第i個單詞的最長詞鏈。

    這樣由于每個單詞進棧出棧分別一次，所以算法的復(fù)雜度是O(n)

我的思路比官方的解法稍微差了一點。遇到此類為題很容易想到用字典樹，程序我沒有寫。最多也只有50萬個結(jié)點，遍歷一次即可出解，應(yīng)該可以AC。