➜ ~

Playing Hacks and Stuffs!

---

Project maintained by h4ckyou Hosted on GitHub Pages — Theme by mattgraham

Longest Common Prefix

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 “”.

So let’s say we have this array of string:

s = ["flower","flow","flight"]

We need to find the longest common prefix which means the longest string that occurs in all string of the array

In this case it’s fl since it occurs in both s[1] and s[2]

One approach we can use is to Brute Force but that isn’t an optimized way because it would take time since we’ll be basically checking each character of the first element in the array with other elements in the array

So here’s a more optimized solution

We can sort the array which would then arrange the elements in increasing order

With it being sorted that means the smallest value would be the first and the largest value would be the last

One important thing here is that due to it being sorted that means it will be sorted lexicographically meaning that it will be arranged in alphabetical order

This can help us limit the longest prefix because of this:

Instead of us searching the whole elements now we know that since it’s sorted we will just search within the first and last element because any other element within it would be less than the last element and would have the same common prefix

So our comparison would be within the first and last element

Here’s my solve script: link

Leetcode Submission Code

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

        first = array[0]
        last = array[len(strs)-1]
        r = ""

        for i in range(len(first)):
            if first[i] != last[i]:
                break
            else:
                r += first[i]

        if len(r) != 0:
            return r
        else:
            return ""