[LeetCode] Longest Common Prefix

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

If there is no common prefix, return an empty string "".

Example:

Input: strs = ["flower","flow","flight"]
Output: "fl"

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

Approach: First approach is obvious bruteforce where we traverse through every string and get the common prefix of all the strings present in the array.

A better approach would be to first sort the strings lexicographically and then we can just compare the first and last strings of the sorted array to find the common prefix of these two strings.

Implementation in C#:

Approach 1: Bruteforce:

    public string LongestCommonPrefix1(string[] strs)

    {

        int length = strs?.Length ?? 0;

        if (length == 0)

        {

            return "";

        }

        if (length == 1)

        {

            return strs[0];

        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < strs[0].Length; ++i)

        {

            char ch = strs[0][i];

            for (int j = 1; j < length; ++j)

            {

                if (i == strs[j].Length || ch != strs[j][i])

                {

                    return sb.ToString();

                }

            }

            sb.Append(ch);

        }

        return sb.ToString();

    }

Approach 2: Soring: 

    public string LongestCommonPrefix(string[] strs)

    {

        int length = strs?.Length ?? 0;

        if (length == 0)

        {

            return "";

        }

        if (length == 1)

        {

            return strs[0];

        }

        Array.Sort(strs);

        StringBuilder sb = new StringBuilder();

        string first = strs[0], second = strs[length - 1];

        int minLength = Math.Min(first.Length, second.Length);

        for (int i = 0; i < minLength; ++i)

        {

            if (first[i] != second[i])

            {

                break;

            }

            sb.Append(first[i]);

        }

        return sb.ToString();

    }

Complexity: O(m * n) for first approach, O(mlogm + O(n))