# Suggest improvements O(n2)

#1

string Solution::longestCommonPrefix(vector &A)
{
string ret = “”;
for(int i=0; i<A[0].size(); i++)
{
int flag=0;
char temp = A[0][i];
for(int j=1; j<A.size(); j++)
{
if(temp!=A[j][i]) flag=1;
}
if(!flag) ret.push_back(temp);
else if(flag) break;
}
return ret;
}

#2

our method is quite similar but there’s no need to continue when you find:
if(temp!=A[j][i]) flag=1;
Check my code to get idea :

string Solution::longestCommonPrefix(vector &A)
{
string ans="";

for(int i=0;i<A[0].length();i++)
{
for(int j=1;j<A.size();j++)
{
if(A[j][i]!=A[0][i]) return ans;
}
ans+=A[0][i];
}
return ans;
}

#3

You can use Trie as follows -

``````struct TrieNode{
int cnt;
vector<struct TrieNode*> child;
};

struct TrieNode* newn()
{
struct TrieNode* cur = new struct TrieNode;
cur->cnt = 0;
cur->child = vector<struct TrieNode*> (52, NULL);
return cur;
}

void insert(struct TrieNode* root, string word)
{
// cout << word << endl;
TrieNode* cur = root;
for(int i = 0 ; i < word.size() ; i++)
{
int cn = word[i]<='z' && word[i]>='a' ? word[i]-'a' : word[i]-'A'+26;
if(cur->child[cn]==NULL)
cur->child[cn] = newn();
cur->child[cn]->cnt++;
cur = cur->child[cn];
}
}

string Solution::longestCommonPrefix(vector<string> &A)
{
TrieNode* root = newn();
for(string &s:A)
insert(root, s);
int len = 0;
TrieNode* cur = root;
for(int i = 0 ; i < A[0].size() ; i++)
{
int cn = A[0][i]<='z' && A[0][i]>='a' ? A[0][i]-'a' : A[0][i]-'A'+26;
cur = cur->child[cn];
if(cur->cnt!=A.size())
break;
len++;
}
return A[0].substr(0, len);
}``````