leetcode账户合并的方法是什么

本篇内容介绍了“leetcode账户合并的方法是什么”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

一、题目内容

给定一个列表 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)

“leetcode账户合并的方法是什么”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！