# [leetcode] 14. Longest Common Prefix

## Question

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

## 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)):
cur: str = strs[i]
for word in strs[1:]:
if i >= len(word) or word[i] != cur:
return word[:i]
return strs
``````