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;
instead to changing flag just return your computed ret string.
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);
}