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賬戶合并的方法是什么”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！