---
tags: data_structure_python
---

# Longest Common Prefix <img src="https://img.shields.io/badge/-easy-brightgreen">

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

<ins>**Example 1:**</ins>

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

<ins>**Example 2:**</ins>

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

**Note:**

All given inputs are in lowercase letters a-z.

## Solution

### Solution 1: Naive approach

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        n = len(strs)
        if n == 0:
            return ""
        
        commonPrefix = strs[0]
                
        for i in range(1, n):
            j, accu, isSameLetter = 0, "", True
            
            minLen = min(len(commonPrefix), len(strs[i]))
                        
            while j < minLen and isSameLetter:
                if commonPrefix[j] == strs[i][j]:
                    accu += commonPrefix[j]
                else:
                    isSameLetter = False
                j += 1       
                
            commonPrefix = accu
                
        return commonPrefix

### Solution 2: Divide and Conquer

class Solution:
    
    def __commonPrefix(self, lcpLeft, lcpRight):
        n, m = len(lcpLeft), len(lcpRight)
        
        minLen = min(n, m)
            
        commonPrefix = ""
        
        for i in range(0, minLen):
            if lcpLeft[i] == lcpRight[i]:
                commonPrefix += lcpLeft[i]
            else:
                return commonPrefix
        
        return commonPrefix
    
    def __longestCommonPrefixDC(self, strs, l, r):
        if l == r:
            return strs[l]
            
        else:
            mid = int((l+r) / 2)
            # Divide.
            lcpLeft = self.__longestCommonPrefixDC(strs, l, mid)
            lcpRight = self.__longestCommonPrefixDC(strs, mid + 1, r)
            # Conquer.
            return self.__commonPrefix(lcpLeft, lcpRight)
        
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # V3: Divide and Conquer.
        if strs == None or len(strs) == 0:
            return ""
        else:
            return self.__longestCommonPrefixDC(strs, 0, len(strs)-1)