Given string array and find the longest common prefix from the array.
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.
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