5.Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

Example:
Input: ["flower","flow","flight"]
Output: "fl"

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Solution 1 : (Word by Word Matching)

class Solution
{

public:
    string getCommonSubstring(string str1, string str2)
    {
        string str = "";
        int i = 0, j = 0;
        while (i < str1.length() && j < str2.length())
        {
            if (str1[i] == str2[j])
            {
                str = str + str1[i];
                i++;
                j++;
            }
            else
            {
                break;
            }
        }
        return str;
    }

    string longestCommonPrefix(vector<string> &strs)
    {

        if (strs.size() == 0)
        {
            return "";
        }
        if (strs.size() == 1)
        {
            return strs[0];
        }

        string s = getCommonSubstring(strs[0], strs[1]);
        for (int i = 2; i < strs.size(); i++)
        {
            s = getCommonSubstring(strs[i], s);
        }

        return s;
    }
};

I have used a property of associativity. By finding the common prefix between 2 pairs. Example:-

LCP(string3,LCP(string1,string2))

Time Complexity: O(n * m)

Solution II: (Divide and Conquer)

class Solution
{
public:
    string findCommon(string lp, string rp)
    {
        int i = 0, j = 0;

        while (i < lp.length() && j < rp.length())
        {
            if (lp[i] == rp[j])
            {
                i++;
                j++;
            }
            else
            {
                break;
            }
        }

        return lp.substr(0, i);
    }
    
    string lcp(vector<string> &v, int start, int end)
    {
        if (start == end)
        {
            return v[start];
        }

        int mid = (start + end) / 2;
        string lp = lcp(v, start, mid);
        string rp = lcp(v, mid + 1, end);

        return findCommon(lp, rp);
    }
    
    string longestCommonPrefix(vector<string> &strs)
    {
        return lcp(strs, 0 , strs.size()-1);
    }
};

Time Complexity: O(m log n)