# [LeetCode] Top Interview 150 Problems Solving # 14 Longest Common Prefix

# **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`.
    

```python
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.