Given an array of strings strs, return the longest string that is a prefix of every string in the array. If the strings share no common prefix, return the empty string "".
Example 1
Input: strs = ["flower","flow","flight"]
Output: "fl"
Example 2
Input: strs = ["dog","racecar","car"]
Output: ""
The first letters already differ.
Constraints
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- Strings contain only lowercase English letters
Hints
Frequently asked at: Amazon, Google, Apple, Infosys, Cognizant
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A simple approach compares the first string against each of the others, trimming the prefix every time, which is fine but can repeat work. Vertical scanning is cleaner: look at column i across all strings. As long as every string has the same character there, the prefix grows by one. The first column with a mismatch, or the end of any string, ends the prefix. Each character is checked at most once.
Algorithm
- Take
first = strs[0]. - For each index
iinfirst, readc = first[i]. - For every other string, if it has length
ior itsi-th character is notc, returnfirst[0:i]. - If the loop finishes, the whole of
firstis the answer.
Time:
O(S), where S is the total number of charactersSpace: O(1) extraInterview tip: Another neat trick: sort the array and compare only the first and last strings, since they differ the most. For repeated queries over a changing set, interviewers may push you towards a trie.
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: first = strs[0] for i, c in enumerate(first): for other in strs[1:]: # Another string ended or has a different character in column i. if i == len(other) or other[i] != c: return first[:i] return firstCtrl + Enter runs the examples