You get an array of strings words. Return the longest prefix that all of them share.
A prefix is the start of a word. For example, "plan" is a prefix of "planet". Every word is also a prefix of itself.
If they share no letters at the start, return the empty string "".
Example 1:
Input: words = ["interview","internet","interval"] Output: "inter" Explanation: All three words start with "inter". Their next letters are v, n and v. These are not all the same, so the prefix ends there.
Example 2:
Input: words = ["sunset","sun","sunsets"] Output: "sun" Explanation: The word "sun" is the whole prefix. The other two words start with it. Nothing longer fits in "sun".
Example 3:
Input: words = ["moon","stars","mars"] Output: "" Explanation: "stars" starts with s. The other two words start with m. So not even the first letter is shared.
Constraints:
wordshas 1 to 10,000 words.- Each word has 0 to 200 letters.
- Each letter is from a to z.
Note:
Your solution should run in O(S) time. S is the total number of letters in words.
Store the words in a trie: a tree with one node per prefix. Words that start the same way share the same path from the root. Mark each node where a word ends.
Walk down from the root. At a node with exactly one child, where no word ends, every word goes on with the same letter. Stop at any other node.
Building the trie visits each letter once, and the walk is at most one word long: O(S) time.
The trie has at most S + 1 nodes, so the extra space is O(S).
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
