Longest Common Prefix
Write a function to find the longest common prefix string among an array of strings. If there is no common prefix, return an empty string `""`. **Core Insight:** Use the first string as the reference prefix. Compare it character by character against every other string. Whenever a mismatch is found — or a string is shorter than the current prefix — truncate the prefix to that position. If the prefix ever becomes empty, return `""` immediately. **Algorithm:** Set `prefix = strs[0]`. For each subsequent string `s`: while `s` does not start with `prefix`, remove the last character of `prefix`. If `prefix` becomes empty, return `""`. Return `prefix` after all strings are processed. **Alternative:** Sort the array lexicographically and only compare the first and last strings — they will have the smallest common prefix among all pairs. **Complexity:** Time O(S) where S is the total number of characters across all strings — each character is examined at most once. Space O(1) extra (ignoring the output string).
Constraints
- •
1 ≤ strs.length ≤ 200 - •
0 ≤ strs[i].length ≤ 200
def longestCommonPrefix(strs: list[str]) -> str:
if not strs:
return ""
prefix = strs[0]
for s in strs[1:]:
while not s.startswith(prefix):
prefix = prefix[:-1]
if not prefix:
return ""
return prefix