题目：给出一个数组，数组中每个元素是一个字符串，要求找出这些字符串最长的公共前缀
思路：这道题可以用字典树的数据结构解决，将每一个字符串按照前缀在内存中保存起来。
class Solution {
private:
struct Node
{
char symbol;
vector<Node*> next;
Node(char val): symbol(val){}
};
public:
string longestCommonPrefix(vector<string> &strs) {
int len = strs.size();
int i,j,strLen,k,nodeSize;
Node* root = new Node('+');
Node* findNode = root;
bool flag;
string LCP = "";
int min = 1000000;
for(i=0; i<len; i++)
{
strLen = strs[i].length();
findNode = root;
flag = true;
min = (min < strLen ? min : strLen);
for(j=0; j<strLen; j++)
{
nodeSize = findNode->next.size();
for(k=0; k<nodeSize && flag; k++)
{
if (strs[i][j] == findNode->next[k]->symbol)
{
break;
}
}
if (k < nodeSize && flag)
{
findNode = findNode->next[k];
continue;
}
flag = false;
Node* newNode = new Node(strs[i][j]);
findNode->next.push_back(newNode);
findNode = newNode;
}
}
findNode = root;
while(findNode->next.size() == 1 && LCP.length() < min)
{
LCP.push_back(findNode->next[0]->symbol);
findNode = findNode->next[0];
}
return LCP;
}
};
其实上面的代码还可以优化，既然是找出最长公共前缀，其实从第二个字符串开始，跟第一个字符串进行类比，一旦没找着同样的字符，就将其截断，不需要再将其保存在树中，代码如下：
class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
int len = strs.size();
int i,j,strLen;
bool flag;
if (len == 0)
{
return "";
}
string LCP = strs[0];
for(i=1; i<len; i++)
{
strLen = strs[i].length();
for(j=0; j<strLen; j++)
{
if (strs[i][j] != LCP[j])
{
break;
}
}
LCP = LCP.substr(0, j);
}
return LCP;
}
};