Given a list of strings words, return the longest string that is a prefix of every word.
If there is no common prefix (or the list is empty) return "".
Examples
Input: words = ["flower", "flow", "flight"]
Output: "fl"
Input: words = ["dog", "racecar", "car"]
Output: ""
Input: words = ["same", "same"]
Output: "same"
Constraints
0 <= len(words) <= 10**4, each word has length<= 1000- Words are lowercase letters (a word may be empty)
- Target:
O(total characters)
Goals
- Recognise the common prefix as the single-child chain at the top of a trie
- Handle an empty list and an empty word correctly