最長公共字首(Longest Common Prefix)
題目：Write a function to find the longest common prefix string amongst an array of strings. 題目連結：https://leetcode.com/problems/longest-common-prefix/ 給出一個字元串數組，找出數組元素的最長公共字首。看到這個題的第一反應是用字典樹(Tire tree)來解決,但是馬上又把這個想法推翻了，原因很簡單，這些數組元素，也就是數組中的字元串的字元沒有範圍規定，是大寫字母？小寫字母？*這類特殊字元，當然也可以這樣做，但是建立字典樹的空間就會很大很大，需要包括所有的列印字元。比較樸素的方法就是對每個字元串就行比對，得出公共字首。 例如： abc abce abcfgh ..... 首先要确定一點，最長公共字首不可能超過數組中長度最短的字元串長度len，然後在這個長度内對比所有字元串，當有任一個字元和其他字元不相等時，傳回。Code如下：
·字典樹
前面提到了字典樹，它是一種字元串進行中一種比較常見的資料結構，它的基本機構如下：
·建立字典樹 特别地，字典樹的root節點是不包含任何資訊的，給定一個字元串s,例如"abcd",首先計算每個字元在next[]的index，這裡，a_index=a-'a'，那麼a在next[]的索引位置為0，如果這個位置為NULL,則為該位置配置設定空間并指派，如果該位置不為NULL，那麼修改該位置的資訊，這裡我們假設struct Tire中的count為簡單的計數，建立字典樹的代碼如下：
建立字典樹的結構大緻如下圖：
·查找 字典樹的查找，按照字典樹的結構從上到下查找，比如給定一個字元串數組，查詢有多少個字元串一'a'開頭，代碼如下：
·釋放字典樹空間
以上便是字典樹的操作，針對不同情況，增加或删除節點的某些資訊，在查找時，針對需要查找的内容從上到下查找，便能得出結果，例如在Longest Common Prefix的問題中，如果數組中的字元串組成限制在小寫或大寫字元中，那麼從上到下查找，當一個節點的next數組有2個及以上的索引位置不為空時，查找便結束，前面查找到的長度len就是公共字元串長度，随便去字元串數組中的一個字元串s，那麼s.substr[0,len]就是公共字首。 字典樹的建立、查找、删除都是和字元串長度密切相關，故，這些操作的時間複雜度應該是O(s.size())=O(n)。