LC 0721 [M] Accounts Merge
Code with Senpai edited this page Sep 28, 2022
·
14 revisions
DFS connected components on the account indexes where the neighbors are the emails
# i is the index of the account and the id, account[0] is the name for that account, account[1:] are the emails for that account
[
["John", "johnsmith@mail.com", "john00@mail.com"], # Account i=0
["John", "johnnybravo@mail.com"], # Account i=1
["John", "johnsmith@mail.com", "john_newyork@mail.com"], # Account i=2, note this has a common email with i=0
["Mary", "mary@mail.com"] # Account i=3
]
# emails_accounts_map of email to account ID
{
"johnsmith@mail.com": [0, 2],
"john00@mail.com": [0],
"johnnybravo@mail.com": [1],
"john_newyork@mail.com": [2],
"mary@mail.com": [3]
}
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
# [[name/account, email1, email2]]
visited = [False] * len(accounts)
email_to_accounts = defaultdict(list) # where we use account index like an account id
res = []
for i, acc in enumerate(accounts): # [name/account, email1, email2], []
for _, email in enumerate(acc[1:]): # [email1, email2]
email_to_accounts[email].append(i)
def dfs(i, emails):
visited[i] = True
acc = accounts[i]
for _, email in enumerate(acc[1:]):
emails.add(email)
for neighbor in email_to_accounts[email]:
if not visited[neighbor]:
dfs(neighbor, emails)
for i, acc in enumerate(accounts):
name, emails = acc[0], set()
if not visited[i]:
dfs(i, emails)
res.append([name] + sorted(emails))
return res
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
# i: [name/account, email1, email2, emailn...]
visited = [False] * len(accounts)
email_to_accounts = defaultdict(list)
res = []
for i, account in enumerate(accounts):
for _, email in enumerate(account[1:]):
email_to_accounts[email].append(i)
def dfs(i, emails):
if visited[i]: return
visited[i] = True
account = accounts[i]
for _, email in enumerate(account[1:]):
emails.add(email)
for neighbor in email_to_accounts[email]:
dfs(neighbor, emails)
for i, account in enumerate(accounts):
if not visited[i]:
name = account[0]
emails = set()
dfs(i, emails)
res.append([name] + sorted(emails))
return res
footer