Python solution with detailed explanation


  • 0
    G

    Accounts Merge https://leetcode.com/problems/accounts-merge/description/

    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):
            visited.add(root)
            component.append(root)
            for nbr in graph[root]:
                if nbr not in visited:
                    self.dfs(nbr, graph, visited, component)
            return
        
        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]:
                            graph[idx].add(nbr)
                            graph[nbr].add(idx)
                    dedupe[email].append(idx)
            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)
                    components.append(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.