Longest Common Prefix

• Problem Statement
  • Example 1
  • Example 2
• Approach 1:
• Approach 2
• Approach 3

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 "". [URL]

Example 1

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

Example 2

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.

Approach 1:

Word based comparison approach

#collapse-hide
from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0:
            return ''
        if len(strs) == 1:
            return strs[0]
        i = 0
        j = i+1
        while(j < len(strs)):
            strs[i] = Solution.lcp_of_two(self, strs[i], strs[j])
            j += 1
    
        return strs[i]
    
    def lcp_of_two(self, ele1, ele2):
        i, j = 0, 0
        while (i < len(ele1) and j < len(ele2)):
            if (ele1[i] == ele2[j]):
                i += 1
                j += 1
            else:    
                break

        lcp = ele1[:i]
        return lcp

sol = Solution()
print(sol.longestCommonPrefix(["flower","flow","flight"]))

fl

print(sol.longestCommonPrefix(["flower","flow","flight"]))

fl

print(sol.longestCommonPrefix(["dog","racecar","car"]))

#collapse-hide
class Solution(object):
    def commonPrefixUtil(self, str1, str2):
        len_str1 = len(str1)
        len_srt2 = len(str2)
        i = j = 0
        while(i < len_str1 and j < len_srt2):
            if str1[i] != str2[j]:
                break
            i += 1
            j += 1
        return str1[:i]
    
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) < 1:
            return ""
        
        prefix = strs[0]
        for i in range(1, len(strs)):
            prefix = self.commonPrefixUtil(prefix, strs[i])
        
        return prefix

sol = Solution()
sol.longestCommonPrefix(["flower","flow","flight"])

'fl'

Approach 2

Character based comparison approach

#collapse-hide
from typing import List

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ''
        minLen = self.finMinimumLenString(strs)
        result = ""
        for i in range(minLen):
            current = strs[0][i]
            for j in range(1, len(strs)):
                if current != strs[j][i]:
                    return result
            result += current
        return result
    
    def finMinimumLenString(self, strs):
        minLen = len(strs[0])
        for i in range(1, len(strs)):
            if len(strs[i]) < minLen:
                minLen = len(strs[i])
        return minLen

sol = Solution()
sol.longestCommonPrefix(["flower","flow","flight"])

'fl'

Approach 3

Character based comparison with Binary Tree implementation

11%3

2