Longest Common Prefix

#leetcode #dsa #theabbie

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 lower-case English letters.

SOLUTION:

# class Solution:
#     def longestCommonPrefix(self, strs: List[str]) -> str:
#         k = min([len(s) for s in strs])
#         i = 0
#         while i <= k and len(set([s[:i] for s in strs])) == 1:
#             i += 1
#         return strs[0][:i-1]

# class Solution:
#     def longestCommonPrefix(self, strs: List[str]) -> str:
#         n = len(strs)
#         prefixes = {}
#         for s in strs:
#             for i in range(len(s) + 1):
#                 prefixes[s[:i]] = prefixes.get(s[:i], 0) + 1
#         return max([(len(k), k, v) for k, v in prefixes.items() if v == n])[1]

# class Solution:
#     def longestCommonPrefix(self, strs: List[str]) -> str:
#         k = min([len(s) for s in strs])
#         i = 0
#         while i < k and len(set([s[i] for s in strs])) == 1:
#             i += 1
#         return strs[0][:i]

class Solution:
    def isLCP(self, strs, k):
        return len(set([s[:k] for s in strs])) == 1

    def longestCommonPrefix(self, strs):
        n = len(strs)
        if n == 0:
            return ""
        beg = 0
        end = min([len(s) for s in strs])
        while beg <= end:
            mid = (beg + end) // 2
            currval = self.isLCP(strs, mid)
            nextval = self.isLCP(strs, mid + 1)
            if (currval and not nextval) or mid >= end:
                return strs[0][:mid]
            elif beg == end:
                break
            elif currval and nextval:
                beg = mid + 1
            else:
                end = mid
        return ""