721. Accounts Merge (Array, Hash Table, String, Depth-First Search, Breadth-First Search, Union Find, Sorting)

링크 - https://leetcode.com/problems/accounts-merge/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

이 문제는 dfs를 통해 풀 수 있는 문제이다. 먼저 각 account의 email들을 first_email를 기준으로 다 이어준다. 그 다음 account를 다시 돌면서 first email이 visited에 있는지 살핀다. 만약 있다면 이미 dfs로 merged된 account이므로 pass하고, 아니면 dfs를 통해 merge를 시작한다.

Code

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        def dfs(account, email):
            account.append(email)
            visited.add(email)

            if email not in adj:
                return

            for neighbor in adj[email]:
                if neighbor not in visited:
                    dfs(account, neighbor)


        adj = defaultdict(list)
        for account in accounts:
            first_email = account[1]
            for email in account[2:]:
                adj[first_email].append(email)
                adj[email].append(first_email)

        visited = set()
        ans = []
        for account in accounts:
            name = account[0]
            first_email = account[1]

            if first_email not in visited:
                merged_account = []
                merged_account.append(name)
                dfs(merged_account, first_email)
                merged_account[1:] = sorted(merged_account[1:])
                ans.append(merged_account)

        return ans

Complexity

여기서 N은 account의 개수이고, K는 각 account들 중 maximum length이다.

Time Complexity: O(NKlogNK)

Space Complexity: O(NK)