Longest Common Prefix (Easy) | LeetCode Practice #4

睡觉

Posted on Jul 12 • Edited on Jul 14

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings strs. Assume that strs only consists of lowercase English letters if it is non-empty. If there is no common prefix, return an empty string “”.

Python

####Horizontal Scanning (Runtime: 5ms, Memory: 12.4MB)
    #DECLARE strs: ARRAY of STRING
class Solution(object):
    def longestCommonPrefix(self, strs):
        prefix = strs[0]
        for i in range(1, len(strs)):
            s = strs[i]
            j = 0
            while j < len(s) and j < len(prefix) and s[j] == prefix[j]:
                j += 1
            prefix = prefix[:j]
        return prefix



####Vertical Scanning (Runtime: 0ms, Memory: 12.5MB)
    #DECLARE strs: ARRAY of STRING
class Solution(object):
    def longestCommonPrefix(self, strs):
        max_length = min(len(s) for s in strs)
        i = 0
        while i < max_length:
            test_char = strs[0][i]
            for j in range(1, len(strs)):
                if strs[j][i] != test_char:
                    return strs[0][:i]
            i += 1
        return strs[0][:i]



####Sorting (Runtime: 0ms, Memory: 12.4MB)
    #DECLARE strs: ARRAY of STRING
class Solution(object):
    def longestCommonPrefix(self, strs):
        strs.sort()
        i = 0
        x = strs[0]
        y = strs[-1]
        while i < len(x) and i < len(y):
            if x[i] == y[i]:
                i += 1
            else:
                break
        return x[0:i]

Enter fullscreen mode Exit fullscreen mode

Thoughts

Sorry, guys. I actually did a pretty terrible job on this one. I spent two days trying to figure out the iteration process in Method 2 (Oh my gosh, my head is full of marshmallows!!!). On the other hand, to be honest, I still haven’t fully mastered Timsort yet. It felt pretty bad to slack off and just use a built-in function instead of coming up with my own solution. But yeah… my brain is just peanut butter right now. Gotta go and get some sleep.