Understanding the Problem

It is simply to find the common prefix in between the strings in the list strs. strs contains strings like strs = ["flower","flow","flight"]. In this case the common prefix will be ”fl” which is included in every string in common. When there is no common prefix, an empty string will be returned.

Approach

The only idea to solve the problem was to go with two for loops with O(n²). The base characters to compare other characters in each string is the first string’s characters.

Solution

There were cases when there is a string in strs but the string is empty like ””, so I returned this when the string length is 1 and it’s empty.

Then try to pile characters in s = ““ if a character in each string is common. Afterwards, it takes steps as follows.

1. The loop occurs in strs[0]. and another loop goes in each string as word.

2. Only if the index i is less than the length of the word, check if the character is common. If not common, I returned s to finish the code.

3. If i is equal or greater than len(word), return s as it is no use running the code any further.

4. Other than that, add the character to s.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 1:
            return strs[0]

        s = ""

        for i in range(len(strs[0])):
            for word in strs:
                if i < len(word): # only when index is within range
                    if word[i] != strs[0][i]:
                        return s
                elif i >= len(word):
                    return s
            s += strs[0][i]
        return s

Reflection

I have looked up other solutions on LeetCode but it was plausible that everyone chose to solve the problem with O(n²) just like I did it. I believe there should be a better solution though.