58. Shared Opening
A search box suggests the text that all candidate words begin with. You are given an array words of lowercase strings, some of which may be empty. Return the longest string that is a prefix of every word in words. If the words have no common beginning, return an empty string.
Compare the words character by character, column by column: as soon as one word is too short or has a different letter in the current column, the shared opening ends just before it. Avoid sorting or building extra copies of the words.
Example 1
- Input:
- words = ["unit","unite","united"]
- Output:
- "unit"
- Explanation:
All three words start with unit, and the first word ends there, so the answer is unit.
Example 2
- Input:
- words = ["north","south"]
- Output:
- ""
- Explanation:
The first letters differ, so there is no common opening and the answer is empty.
Constraints
1 ≤ words.length ≤ 200
0 ≤ words[i].length ≤ 200
words[i] contains only lowercase English letters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(total characters)
- Space
- O(1)