目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。

现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。

合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。账户本身可以以任意顺序返回。

示例 1：

输入：
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
输出：
[["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
解释：
第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "johnsmith@mail.com"。 
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
可以以任何顺序返回这些列表，例如答案 [['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']] 也是正确的。

提示：

accounts的长度将在[1，1000]的范围内。
accounts[i]的长度将在[1，10]的范围内。
accounts[i][j]的长度将在[1，30]的范围内。

二、解题思路

首先，建立一个图graph和字典email_dict，email_dict里存储邮箱对应的名字name作为结果集res每个列表的第一个元素，graph里存储邮箱间的两两对应关系。

其次，DFS，对graph的邮箱两两判断，存在则添加至tmp，visited集合加入对应的邮箱，之后则不在查看该邮箱。

最后对加入的邮箱排序，放在name后面即可。

三、代码

  

   

    

     

    
    

     

      from collections import defaultdict
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def accountsMerge(self, accounts: list) -> list:
     
    
   

    

     

    
    

     

       graph = defaultdict(set)
     
    
   

    

     

    
    

     

       email_dict = defaultdict()
     
    
   

    

     

    
    

     
 for account in accounts:
     
    
   

    

     

    
    

     

       name = account[0]
     
    
   

    

     

    
    

     

       emails = account[1:]
     
    
   

    

     

    
    

     

       first_email = emails[0]
     
    
   

    

     

    
    

     
 for email in emails:
     
    
   

    

     

    
    

     

       email_dict[email] = name
     
    
   

    

     

    
    

     

       graph[first_email].add(email)
     
    
   

    

     

    
    

     

       graph[email].add(first_email)
     
    
   

    

     

    
    

     

       visited = set()
     
    
   

    

     

    
    

     

       res = []
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def dfs(email, tmp):
     
    
   

    

     

    
    

     

       tmp.append(email)
     
    
   

    

     

    
    

     
 for email2 in graph[email]:
     
    
   

    

     

    
    

     
 if email2 not in visited:
     
    
   

    

     

    
    

     

       visited.add(email2)
     
    
   

    

     

    
    

     

       tmp = dfs(email2, tmp)
     
    
   

    

     

    
    

     
 return tmp
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 for email in graph:
     
    
   

    

     

    
    

     
 if email not in visited:
     
    
   

    

     

    
    

     

       visited.add(email)
     
    
   

    

     

    
    

     

       tmp = dfs(email, [])
     
    
   

    

     

    
    

     

       res.append([email_dict[email]] + sorted(tmp))
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 return res
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       accounts = [["John", "johnsmith@mail.com", "john00@mail.com"],
     
    
   

    

     

    
    

     

       ["John", "johnnybravo@mail.com"],
     
    
   

    

     

    
    

     

       ["John", "johnsmith@mail.com", "john_newyork@mail.com"],
     
    
   

    

     

    
    

     

       ["Mary", "mary@mail.com"]]
     
    
   

    

     

    
    

     

       ans = s.accountsMerge(accounts)
     
    
   

    

     

    
    

     

       print(ans)
     
    
   

    

     

    
    

     
 
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/112765637