[LeetCode] 14. Longest Common Prefix

1. Description

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 "".

 

constraints :

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.

 

2. Algorithms

We will find the longest common prefix by sorting the input list according to the length of each element. The sorted list has the smallest length of the string at the front.

 

As a way of finding the greatest common divisor, we consider the first element as a longest common prefix and compare it with the rest to erase the noncommon prefix substring.

 

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

strs.sort() = ["flow", "flight", "flower"]

longest common prefix = flow 

while longest common prefix not in strs[i], 
	1. longest common prefix = longest common prefix[:-1]

 

1. Start
2. Sort the input list according to the length of elements
3. Declare variable lcp(longest common prefix) and initialize it to first element of strs
4. Repeat the steps through the elements of strs[1:]
   1. Repeat the steps until lcp becomes common prefix of current element
      1. To check whether lcp is common prefix of current element, we will use str.startswith() method
      2. Update lcp to lcp[:-1]
5. Return lcp
6. End

 

3. Codes

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

        lcp = strs[0]
        for i in range(1, len(strs)):
            while not strs[i].startswith(lcp): 
                lcp = lcp[:-1]
        return lcp

 

4. Conclusion

 

Time Complexity : \(O(N)\)

Space Complexity : \(O(N)\)