編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。

如果不存在公共前綴，返回空字符串 “”。

示例 1：
輸入：strs = [“flower”,“flow”,“flight”]
輸出：“fl”

示例 2：
輸入：strs = [“dog”,“racecar”,“car”]
輸出：“”
解釋：輸入不存在公共前綴。

提示：
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 如果非空，則僅由小寫英文字母組成

class Solution {
private:struct dt { vector<dt*> children;bool isEnd;dt() : children(26, nullptr), isEnd(false) {}};dt* root;
public:Solution() {root = new dt();  // 初始化根節(jié)點(diǎn)}string longestCommonPrefix(vector<string>& strs) {for(string word : strs){if(word.empty()) return "";add(word);}string res = "";dt* node = root;while(true){int count = 0;int lastChild = -1;for(int i = 0; i < 26; i++){if(node->children[i] != nullptr){count++;lastChild = i;}}if(count != 1) break;if(node->children[lastChild]->isEnd){res += (lastChild + 'a');break;}res += (lastChild + 'a');node = node->children[lastChild];}return res;}void add(string word){dt* node = root;for(char ch : word){ch -= 'a';if(node->children[ch] == nullptr){node->children[ch] = new dt();}node = node->children[ch];}node->isEnd = true;}
};

我們可以使用tried樹來解決這道題，首先先將所有strs的word構(gòu)造出一個字典樹。接下來我們從字典樹的根節(jié)點(diǎn)不斷向下查找，我們看他有幾個子節(jié)點(diǎn)，如果有多個子節(jié)點(diǎn)，就說明不需要繼續(xù)添加字符了，因?yàn)橹挥挟?dāng)children的數(shù)量為1個的時候，說明是公共前綴。

然后我們還要檢查我們選擇的下一個節(jié)點(diǎn)是不是某個word的結(jié)尾，如果是的話，就將其添加到res后，停止繼續(xù)查找添加。