A phone exported its address book as contacts, a list of entries. Each entry is a list whose first element is a person's name and whose remaining elements (possibly none) are phone numbers as strings. Two entries belong to the same person if they share at least one phone number, directly or through a chain of other entries. All entries of the same person carry the same name, but two different people may share a name.
Return the merged address book: one entry per person, formatted as [name, phone_1, phone_2, ...] with the phone numbers in ascending string order and without duplicates. Sort the entries themselves in ascending order (Python's default list comparison).
Examples
Input: contacts = [["Ana", "111", "222"], ["Ana", "333"], ["Ana", "222", "444"], ["Bo", "555"]]
Output: [["Ana", "111", "222", "444"], ["Ana", "333"], ["Bo", "555"]]
Explanation: the first and third entries share "222"; the second Ana is a different person.
Input: contacts = [["Cy", "9"], ["Cy", "9"]]
Output: [["Cy", "9"]]
Constraints
0 <= len(contacts) <= 3000, each entry has at most 10 phone numbers, total numbers<= 10**4- Target: O(T * alpha(T) + T log T) time, where T is the total number of phone numbers.
Goals
- Union entries through a shared-key map instead of pairwise comparison
- Aggregate the members of each set and produce canonical sorted output