【数据结构-字典树】力扣14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

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

示例 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();  // 初始化根节点}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构造出一个字典树。接下来我们从字典树的根节点不断向下查找，我们看他有几个子节点，如果有多个子节点，就说明不需要继续添加字符了，因为只有当children的数量为1个的时候，说明是公共前缀。

然后我们还要检查我们选择的下一个节点是不是某个word的结尾，如果是的话，就将其添加到res后，停止继续查找添加。