Longest Common Prefix
Easy· vertical scan
Problem
Given a list of strings, return the longest prefix that every string shares. If they have nothing in common at the start, return an empty string.
Examples
Input: strs = ["interview","internet","interval"]
Output: "inter"
All three words begin with "inter" and differ at the next character.
Input: strs = ["cat","dog"]
Output: ""
Constraints
- • 1 <= strs.length <= 200
- • 0 <= strs[i].length <= 200
- • Lowercase English letters only
Hints & approach
Hint 1
The answer can be no longer than the shortest string.
Hint 2
Compare characters column by column across all strings.
Approachtry the hints first
Scan column by column: for each index i, check that every string has a character at i and that it equals the first string's character at i. Stop at the first mismatch or when any string runs out, and return the first string's prefix up to that index. An alternative is to sort the list and compare only the first and last strings, since they differ the most.
Time O(total characters) · Space O(1)