Python solution with detailed explanation

  • 0

    Accounts Merge

    Finding Components Using DFS

    • Build a undirectional graph by iterating all the accounts. The index of the sublist within the accounts array can be used as account id. If an email was found in accounts 1, 2 and is found again in account 3, then 3 is a nbr of 1, 2 and 1,2 are nbr of 3.
    • Once we built the graph, simply run dfs on it and get all the components.
    • Once we have the components, identify all the unique emails and format the result. Notice the use of itertools in formatting.
    from collections import defaultdict
    from itertools import chain
    class Solution(object):
        def dfs(self, root, graph, visited, component):
            for nbr in graph[root]:
                if nbr not in visited:
                    self.dfs(nbr, graph, visited, component)
        def build_graph(self, accounts):
            graph, dedupe = {}, defaultdict(list)
            for idx, account in enumerate(accounts):
                graph[idx] = set([])
                for email in account[1:]:
                    if email in dedupe:
                        for nbr in dedupe[email]:
            return graph
        def identify_components(self, graph):
            visited = set([])
            components = []
            for root in graph.keys():
                if root not in visited:
                    component = []
                    self.dfs(root, graph, visited, component)
            return components
        def format_result(self, components, accounts):
            result = []
            for component in components:
                emails  = sorted(list(set(chain(*(accounts[i][1:] for i in component)))))
                result.append([accounts[component[0]][0]] + emails)
            return result
        def accountsMerge(self, accounts):
            :type accounts: List[List[str]]
            :rtype: List[List[str]]
            graph = self.build_graph(accounts)
            components = self.identify_components(graph)
            result = self.format_result(components, accounts)
            return result

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.