LeetCode: Longest Common Prefix

Return the longest common prefix of an array of strings.

Posted on LeetCode Python

Brute Force Solution

Runtime

3 ms | Beats 26.38% 

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix = ""


        def all_matching(i: int) -> bool:
            for j in range(1, len(strs)):
                if strs[j][i] != strs[0][i]:
                    return ""
            return strs[0][i]


        i = 0
        while i >= 0:
            try:
                char = all_matching(i)


                if char != "":
                    prefix += char
                    i += 1
                else:
                    break
            except IndexError:
                break


        return prefix

Second Solution

For my second solution, I used Python’s built-in zip function to group characters from each string by index. Then I used a regular expression to check that all characters in each group are the same.

Runtime

0 ms | Beats 100.00% 

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix = ""


        for t in zip(*strs):
            s = "".join(t)
            if re.match(r"^(.)\1*$", s):
                prefix += s[0]
            else:
                break


        return prefix