KK's blog

每天积累多一些

0%

LeetCode 721 Accounts Merge

Posted on Edited on Disqus:

LeetCode



Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1:

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”]]
Explanation:
The first and second John’s are the same person as they have the common email “johnsmith@mail.com”.
The third John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [[‘Mary’, ‘mary@mail.com’], [‘John’, ‘johnnybravo@mail.com’],
[‘John’, ‘john00@mail.com’, ‘john_newyork@mail.com’, ‘johnsmith@mail.com’]] would still be accepted.


Example 2:

Input: accounts = [[“Gabe”,”Gabe0@m.co”,”Gabe3@m.co”,”Gabe1@m.co”],[“Kevin”,”Kevin3@m.co”,”Kevin5@m.co”,”Kevin0@m.co”],[“Ethan”,”Ethan5@m.co”,”Ethan4@m.co”,”Ethan0@m.co”],[“Hanzo”,”Hanzo3@m.co”,”Hanzo1@m.co”,”Hanzo0@m.co”],[“Fern”,”Fern5@m.co”,”Fern1@m.co”,”Fern0@m.co”]]
Output: [[“Ethan”,”Ethan0@m.co”,”Ethan4@m.co”,”Ethan5@m.co”],[“Gabe”,”Gabe0@m.co”,”Gabe1@m.co”,”Gabe3@m.co”],[“Hanzo”,”Hanzo0@m.co”,”Hanzo1@m.co”,”Hanzo3@m.co”],[“Kevin”,”Kevin0@m.co”,”Kevin3@m.co”,”Kevin5@m.co”],[“Fern”,”Fern0@m.co”,”Fern1@m.co”,”Fern5@m.co”]]


Constraints:

1 <= accounts.length <= 1000 2 <= accounts[i].length <= 10
1 <= accounts[i][j] <= 30 accounts[i][0] consists of English letters.
* accounts[i][j] (for j > 0) is a valid email.

题目大意：

每个人都有一堆邮件，根据邮件是否相同判断是否同一个人，合并同一个人的所有邮件。

BFS解题思路(推荐)：

根据输入建图，然后类似于Num of island从某一个邮件出发用BFS找连通的所有邮件，迭代所有邮件，全局visited来记录访问过的，这点跟Num of island一样。

解题步骤：

N/A

注意事项：

  1. 图的初始化，要记得没有边的图要加入到邻接表中，注意不存在的时候才加入，否则会覆盖现有的邻接表Line 8 - 9
  2. 处理名字(第一个元素)，名字对确定是否连通没有任何作用，只需要加入到最后结果即可
  3. 有重复邮件，所以一开始去重。结果按同一账号内按字母排序

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
	for li in accounts:
		li[:] = [li[0]] + list(set(li[1:]))
	graph = collections.defaultdict(list)
	name_dict = collections.defaultdict(str)
	for li in accounts:
		name_dict[li[1]] = li[0]
		if li[1] not in graph:
			graph[li[1]] = [] # remember single email
		for i in range(2, len(li)):
			graph[li[1]].append(li[i])
			graph[li[i]].append(li[1])
	res, visited = [], set()
	for email in graph.keys():
		sub_res = self.bfs(graph, email, visited, name_dict)
		if sub_res:
			res.append(sub_res)
	return res

def bfs(self, graph, start, visited, name_dict):
	if start in visited:
		return
	res, name = [], ''
	queue = collections.deque([start])
	visited.add(start)
	while queue:
		node = queue.popleft()
		res.append(node)
		if node in name_dict:
			name = name_dict[node]
		for neighbor in graph[node]:
			if neighbor in visited:
				continue
			queue.append(neighbor)
			visited.add(neighbor)
	res.sort()
	res.insert(0, name)
	return res

算法分析：

时间复杂度为O(nklognk)，空间复杂度O(nk), n, k分别账号数，每个账号的邮件数, 因为结果需要按字母排序

UnionFind算法II解题思路(不推荐)：

这题很容易想到用连通集做，但其实连通集应用条件为动态求连通集个数。这题是静态求连通数，所以类似于L200 Num of island可以用DFS或者BFS。

注意事项：

  1. union只做每个list里面的，而list之间相同的邮件不用做union，因为既然相同自动做了
  2. 模板的问题，见UnionFind里的注意事项： if self.parent[email] != email, self.parent[parent] = parent2
  3. 处理名字
  4. 有重复邮件

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution(TestCases):

    def accountsMerge2(self, accounts: List[List[str]]) -> List[List[str]]:
        for li in accounts:
            li[::] = [li[0]] + list(set(li[1:]))
        uf = UnionFind(accounts)

        for li in accounts:
            for i in range(2, len(li)):
                uf.union(li[i - 1], li[i])

        visited = set()
        res = collections.defaultdict(list)
        name_dict = collections.defaultdict(str)
        for li in accounts:
            name_dict[uf.find(li[1])] = li[0]
            for email in li[1:]:
                if email in visited:  # remember
                    continue
                res[uf.find(email)].append(email)
                visited.add(email)
        for _id, li in res.items():
            li.sort()
            li.insert(0, name_dict[_id])
        return list(res.values())

class UnionFind:

    def __init__(self, email_list):
        self.parent = collections.defaultdict(str)
        for i, li in enumerate(email_list):
            for email in li[1:]:
                self.parent[email] = email

    def find(self, email):
        if self.parent[email] != email:  # if statement
            self.parent[email] = self.find(self.parent[email])
        return self.parent[email]

    def union(self, email, email2):
        parent = self.find(email)
        parent2 = self.find(email2)
        if parent != parent2:
            self.parent[parent] = parent2 # remember not self.parent[email] = email2

算法分析：

时间复杂度为O(nklognk)，空间复杂度O(nk), n, k分别账号数，每个账号的邮件数

Free mock interview