849. Merge the Address Books
A hiking club kept many address books. Each book in accounts is a list [owner, email1, email2, ...]: the owner's name followed by one or more email addresses. Two books belong to the same person when they share at least one email address, either directly or through a chain of other books. Such books must be merged into a single book. Books that share no email stay separate, even when their owners have the same name; books that are linked through a shared email always carry the same owner name.
Return the merged books. Each merged book is a list whose first element is the owner name, followed by every distinct email of that person in ascending ASCII (plain string) order. The outer list may be returned in any order, but the order inside each book must be exactly as described.
Example 1
- Input:
- accounts = [["mia","[email protected]","[email protected]"],["leo","[email protected]"],["mia","[email protected]","[email protected]"]]
- Output:
- [["leo","[email protected]"],["mia","[email protected]","[email protected]","[email protected]"]]
- Explanation:
The first and third books share
[email protected], so they merge into one list of three sorted emails; leo's book stays alone.
Example 2
- Input:
- accounts = [["sam","[email protected]"],["sam","[email protected]"]]
- Output:
- [["sam","[email protected]"],["sam","[email protected]"]]
- Explanation:
The two books have the same owner name but no common email, so they are different people and stay separate.
Example 3
- Input:
- accounts = [["kim","[email protected]"],["kim","[email protected]","[email protected]"],["kim","[email protected]","[email protected]"]]
- Output:
- [["kim","[email protected]","[email protected]","[email protected]"]]
- Explanation:
The first book links to the second through
[email protected], and the second to the third through[email protected], so all three merge intokim, k1, k2, k3.
Constraints
- 1 ≤ accounts.length ≤ 104
- 1 ≤ accounts[i].length ≤ 11 (a name plus 1 to 10 emails); an email may repeat inside one book
- Names are 1 to 10 lowercase letters or digits; emails are 1 to 40 characters from lowercase letters, digits, '@' and '.'
- Books sharing an email have the same name
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(E log E)
- Space
- O(E)