An autocomplete box wants to fill in as much as it safely can: if every suggestion starts with the same letters, it can type them for the user straight away.
Write shared_beginning(words) -> str that returns the longest string that every word in words starts with. If the words don't all start with the same letter, return "".
shared_beginning(["interval", "internet", "interior"]) # "inter"
shared_beginning(["dog", "cat"]) # ""
shared_beginning(["solo"]) # "solo"
shared_beginning(["same", "same"]) # "same"
Constraints:
1 <= len(words) <= 2 * 10^5- Each word has
0to10^6characters, and the total length of all words is at most2 * 10^6. - Words contain only lowercase English letters.
Aim for O(total length) time. Building and testing every candidate beginning separately (w.startswith(words[0][:k]) for k = 1, 2, ...) is quadratic in the answer's length, which is too slow when two long words agree almost everywhere.
Show hint
The answer can never be longer than the shortest word. Compare the words column by column, position 0 in every word, then position 1, and stop at the first position where they disagree or a word runs out.