721. Accounts Merge

Medium

Description

給定帳戶列表 accounts，每個帳戶第一個元素是名字，其餘是該帳戶的電子信箱。若兩個帳戶有相同的電子信箱，則屬於同一個人。合併所有屬於同一個人的帳戶，信箱按字典序排列。

Example:

Input: accounts = [[“John”,“johnsmith@mail.com”,“john_newyork@mail.com”],[“John”,“johnsmith@mail.com”,“john00@mail.com”],[“Mary”,“mary@mail.com”],[“John”,“johnnybravo@mail.com”]] Output: [[“John”,“john00@mail.com”,“john_newyork@mail.com”,“johnsmith@mail.com”],[“Mary”,“mary@mail.com”],[“John”,“johnnybravo@mail.com”]]

Intuition#

將每個信箱視為節點，同一帳戶的信箱互相連接，用 Union-Find 或 DFS 找連通分量。

同一帳戶的信箱屬於同一個人，形成連通分量
不同帳戶若有相同信箱，也應合併
找出所有連通分量後，按要求格式輸出

Approaches#

1: DFS#

概念: 建立信箱的鄰接表，DFS 找出所有連通分量
時間複雜度: O(N * K * log(N * K))，N 為帳戶數，K 為平均信箱數
空間複雜度: O(N * K)

class Solution {
    fun accountsMerge(accounts: List<List<String>>): List<List<String>> {
        val graph = HashMap<String, MutableSet<String>>()
        val emailToName = HashMap<String, String>()

        for (account in accounts) {
            val name = account[0]
            for (i in 1 until account.size) {
                emailToName[account[i]] = name
                graph.getOrPut(account[i]) { mutableSetOf() }
                if (i > 1) {
                    graph[account[1]]!!.add(account[i])
                    graph[account[i]]!!.add(account[1])
                }
            }
        }

        val visited = HashSet<String>()
        val result = mutableListOf<List<String>>()

        for (email in graph.keys) {
            if (email in visited) continue
            val component = mutableListOf<String>()
            val stack = ArrayDeque<String>()
            stack.add(email)
            while (stack.isNotEmpty()) {
                val cur = stack.removeLast()
                if (cur in visited) continue
                visited.add(cur)
                component.add(cur)
                for (next in graph[cur]!!) {
                    if (next !in visited) stack.add(next)
                }
            }
            component.sort()
            result.add(listOf(emailToName[email]!!) + component)
        }
        return result
    }
}

⭐2: Union-Find#

概念: 用 Union-Find 將同帳戶的信箱合併，最後按根節點分組
時間複雜度: O(N * K * α(N * K))
空間複雜度: O(N * K)

class Solution {
    private val parent = HashMap<String, String>()

    fun accountsMerge(accounts: List<List<String>>): List<List<String>> {
        val emailToName = HashMap<String, String>()

        for (account in accounts) {
            val name = account[0]
            for (i in 1 until account.size) {
                emailToName[account[i]] = name
                parent.putIfAbsent(account[i], account[i])
                if (i > 1) union(account[1], account[i])
            }
        }

        val groups = HashMap<String, MutableList<String>>()
        for (email in parent.keys) {
            val root = find(email)
            groups.getOrPut(root) { mutableListOf() }.add(email)
        }

        return groups.values.map { emails ->
            emails.sort()
            listOf(emailToName[emails[0]]!!) + emails
        }
    }

    private fun find(x: String): String {
        if (parent[x] != x) parent[x] = find(parent[x]!!)
        return parent[x]!!
    }

    private fun union(x: String, y: String) {
        val px = find(x)
        val py = find(y)
        if (px != py) parent[px] = py
    }
}

🔑 Takeaways#

Pattern: 連通分量合併 – Union-Find 處理等價類
關鍵技巧: 只需將每個帳戶的信箱與第一個信箱做 union，不需兩兩 union；注意最後要按字典序排列信箱