14. Longest Common Prefix

Problem Statement

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 1:

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

Example 2:

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

Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters.

Intuition

BruteForce
Take for all strings check prefix

Optimal:

Sort and just check for first and last
eg - fl ...... flower
Directly just check

Links

https://leetcode.com/problems/longest-common-prefix/description/

Video Links

Approach 1:

Brute

C++

class Solution {
public:
    string longestCommonPrefix(vector<string>& a) {
        
        string monk=a[0];
        int size=0;
        bool flag=true;
        int n=a.size();

        for(int i=0;i<monk.size();i++){
            for(int j=0;j<n;j++){
                if(monk[i]!=a[j][i]){
                    flag=false;
                    break;
                }
            }

            if(flag==false)
                break;

            size++;

        }

        if(size==0) return "";
        
        else
            return monk.substr(0,size);
        




    }
};

Approach 2:

optimal

C++

class Solution {
public:
    string longestCommonPrefix(vector<string>& str) {
        int n = str.size();
        sort(str.begin(), str.end());
        string first = str[0];
        string last = str[n-1];
        int size = 0;

        for(int i=0; i<first.size(); i++){
            if(first[i] == last[i])
                size++;

            else
                break;
        }

        return first.substr(0, size);
    }
};

Approach 3:

C++

Approach 4:

C++