Skip to main content

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 "".

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
   public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = strs.size();
        string s = strs[0];
        int j = s.length() - 1;
        for (int i = 1; i < n; i++) {
            for (int k = 0; k <= j; k++) {
                if (strs[i][k] != s[k]) {
                    j = k - 1;
                    break;
                }
            }
        }
        if (j < 0) return "";
        return string(s.begin(), s.begin() + j + 1);
    }
};