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 ""
Top comments (0)