[leetcode] 14. Longest Common Prefix

Question

Given string array and find the longest common prefix from the array.

• 14. Longest Common Prefix

Solution

Vertically scanning way came to me. The idea is that I checked the letter of each string vertically from the beginning of the string. For example, if the given array was "flower" and "flow", I first check the first letter of each word, which means "f" and then I check the second letter. If a letter doesn't match others or the length of a word is out, I return the current matched string.

Submission

Here is the result.

Runtime: 43 ms, faster than 27.40% of Python3 online submissions for Longest Common Prefix.
Memory Usage: 14.4 MB, less than 25.69% of Python3 online submissions for Longest Common Prefix.

Time complexity: O(S) S is the sum of all letters in every word.
Space complexity: O(1)

In the worst case, I need to check all letters so time complexity is O(S). I need one variable to save a current letter so space is O(1)

Here is my python code.

# Time complexity: O(S)
# Space complexity: O(1)
def longestCommonPrefix(self, strs: List[str]) -> str:
    for i in range(len(strs[0])):
        cur: str = strs[0][i]
        for word in strs[1:]:
            if i >= len(word) or word[i] != cur:
                return word[:i]
    return strs[0]