题目链接：https://leetcode.com/problems/longest-common-prefix/
Write a function to find the longest common prefix string amongst an array of strings.（最长公共前缀）
解题思路：字典树。以任一串去查找，找到最长的且匹配数为n的即可，水题。
struct Trie{ Trie *next[26]; int cnt; //string str; }*root; int n; string ans; void insert(string s){ Trie *p = root,*pnew; for(int i = 0;i < s.size();++ i){ int x = s[i] - 'a'; if(p->next[x] == NULL){ pnew = new Trie; pnew->cnt = 1; for(int j = 0;j < 26;++ j){ pnew->next[j] = NULL; } p->next[x] = pnew; } else p->next[x]->cnt++; p=p->next[x]; } } int search(string s){ Trie *p = root; bool f = 0; for(int i = 0;i < s.size();++ i){ int x = s[i] - 'a'; if(p->next[x] == NULL) return 0; if(p->next[x]->cnt == n){ ans = s.substr(0,i+1); f = 1; } p = p->next[x]; } return f; } void init(){ root = new Trie; root->cnt = 0; for(int i = 0;i < 26;++ i){ root->next[i] = NULL; } } class Solution { public: string longestCommonPrefix(vector<string>& strs) { n = strs.size(); if(!n) return ans = ""; init(); for(int i = 0;i < n;++ i){ insert(strs[i]); } if(!search(strs[0])) return ans = ""; return ans; } };
