Longest Shared Opening
EasyTries & StringsFree
Problem
A log tool wants to collapse a group of file names by the beginning they all have in common. Given a non-empty list of strings words, return the longest string that is a prefix of every word.
If the words share no beginning, return the empty string.
Example 1
- Input:
- words = ["interview", "internet", "interval"]
- Output:
- "inter"
All three start with "inter"; the next letters (v, n, v) disagree.
Example 2
- Input:
- words = ["mango", "melon", "maple"]
- Output:
- "m"
Example 3
- Input:
- words = ["solo"]
- Output:
- "solo"
Constraints
- 1 ≤ words.length ≤ 200
- 0 ≤ words[i].length ≤ 200
- Words are lowercase English letters.
Hint
Show the first hint
The answer can never be longer than the first word.
Walkthrough
How to approach it
01Clarify before coding
- Can a word be empty? Yes, and then the answer is the empty string.
- Is the comparison case-sensitive? Only lowercase letters appear, so it does not matter here.
- Do I return the prefix or its length? The prefix string itself.
02Brute force
Try every prefix of the first word from longest to shortest and check it against all words with startsWith.
Cost: O(L²·n) for n words of length L: each of L candidates is checked against n words at O(L) each.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.