LeetCode 14. 最长公共前缀
原题链接
简单
作者:
linux_2019
,
2019-09-19 15:31:12
,
所有人可见
,
阅读 872
C++ 代码
class Solution {
public:
int trie[2000][26];
int idx;
int insert(string & s)
{
int p=0;
int cnt=0;
for(int i=0;i<s.size();i++)
{
int ch=s[i]-'a';
if(!trie[p][ch])
trie[p][ch]=++idx;
else
{
cnt++;
}
p=trie[p][ch];
}
return cnt;
}
string longestCommonPrefix(vector<string>& strs) {
idx=0;
if (strs.size()==0) return "";
if(strs.size()==1) return strs[0];
memset(trie,0,sizeof trie);
insert(strs[0]);
int res=INT_MAX;
for(int i=1;i<strs.size();i++)
{
res=min(res,insert(strs[i]));
}
string ans;
for(int i=0;i<res;i++)
ans+=strs[0][i];
return ans;
}
};