[leetcode #721] Accounts Merge

Problem

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.

Idea

복잡하지만 쉬운 문제인 줄 알았는데 아니었다.

처음엔 각 account의 소유주를 key로 하고, 각 소유주의 이름 하에 email list의 list를 value로 하는 map을 이용해 풀려고 했다. account 리스트를 돌면서 이름이 똑같을 경우 email list에 동일한 이메일이 있으면 list를 merge하는 방법으로 구현하려고 했던 것이다. 하지만 이와 같은 방식으로 문제를 풀 경우 merge가 안 된 list가 나올 가능성이 있으므로 올바른 방식이 아니었다.

LeetCode solution에서 제시한 방법은 그래프를 이용한 것이다.

우선 주어진 노드를 차례로 돌면서 vertex 사이를 연결하는 edge를 전부 구해 list에 저장한다. 해당 list는 각 account의 첫 번째 이메일이 key인 map에 value로 저장된다.

이후 주어진 노드를 다시 돌면서 DFS를 통해 서로 연결된 이메일을 하나로 합친다. 이름을 첫 번째 element로 리스트에 저장한 후, 첫번째 이메일과 전체 메일 리스트를 DFS의 시작점으로 정한다.

DFS의 인자로 들어온 첫 번째 메일은 visited로 표시되고 메일 리스트에도 더해진다. 이후 앞 단계에서 만든 edge list를 돌면서 해당 메일이 아직 visited 표시가 되어 있지 않다면 해당 메일을 인자로 해서 DFS를 돌린다. DFS에서 주의할 점은 이미 탐색이 끝난 메일인 경우 DFS를 돌리지 않는다는 것이다.

DFS가 끝나면 모든 edge를 다 탐색하게 되며, 하나의 mail 리스트가 만들어진다. 이 리스트를 정렬한 뒤, mergedAccounts 리스트에 더하면 된다. 모든 account를 돌고난 뒤 mergedAccounts를 리턴하면 끝이다.

Solution

내가 다시 푼 Solution

class Solution {
    HashSet<String> visited;
    Map<String, List<String>> adjacent;

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        visited = new HashSet<>();
        adjacent = new HashMap<>();

        for (List<String> account : accounts) {
            String firstEmail = account.get(1);
            if (!adjacent.containsKey(firstEmail)) {
                adjacent.put(firstEmail, new ArrayList<>());
            }
            List<String> adjacentList = adjacent.get(firstEmail);
            for (int i=2; i < account.size(); i++) {
                String email = account.get(i);
                adjacentList.add(email);

                if (!adjacent.containsKey(email)) {
                    adjacent.put(email, new ArrayList<>());
                }
                List<String> otherList = adjacent.get(email);
                otherList.add(firstEmail);
            }
        }

        List<List<String>> mergedAccounts = new ArrayList<>();

        for (List<String> account : accounts) {
            String accountName = account.get(0);
            String accountEmail = account.get(1);

            if (visited.contains(accountEmail))
                continue;

            List<String> mergedAccount = new ArrayList<>();
            mergedAccount.add(accountName);
            DFS(mergedAccount, accountEmail);
            Collections.sort(mergedAccount.subList(1, mergedAccount.size()));
            mergedAccounts.add(mergedAccount);
        }

        return mergedAccounts;
    }

    private void DFS(List<String> mergedList, String mail) {        
        visited.add(mail);
        mergedList.add(mail);
        List<String> adjacentList = adjacent.get(mail);

        for (String next : adjacentList) {
            if (visited.contains(next))
                continue;
            DFS(mergedList, next);
        }
    }
}

Leetcode Solution

class Solution {
    HashSet<String> visited = new HashSet<>();
    Map<String, List<String>> adjacent = new HashMap<String, List<String>>();

    private void DFS(List<String> mergedAccount, String email) {
        visited.add(email);
        // Add the email vector that contains the current component's emails
        mergedAccount.add(email);

        if (!adjacent.containsKey(email)) {
            return;
        }

        for (String neighbor : adjacent.get(email)) {
            if (!visited.contains(neighbor)) {
                DFS(mergedAccount, neighbor);
            }
        }
    }

    public List<List<String>> accountsMerge(List<List<String>> accountList) {
        int accountListSize = accountList.size();

        for (List<String> account : accountList) {
            int accountSize = account.size();

            // Building adjacency list
            // Adding edge between first email to all other emails in the account
            String accountFirstEmail = account.get(1);
            for (int j = 2; j < accountSize; j++) {
                String accountEmail = account.get(j);

                if (!adjacent.containsKey(accountFirstEmail)) {
                    adjacent.put(accountFirstEmail, new ArrayList<String>());
                }
                adjacent.get(accountFirstEmail).add(accountEmail);

                if (!adjacent.containsKey(accountEmail)) {
                    adjacent.put(accountEmail, new ArrayList<String>());
                }
                adjacent.get(accountEmail).add(accountFirstEmail);
            }
        }

        // Traverse over all th accounts to store components
        List<List<String>> mergedAccounts = new ArrayList<>();
        for (List<String> account : accountList) {
            String accountName = account.get(0);
            String accountFirstEmail = account.get(1);

            // If email is visited, then it's a part of different component
            // Hence perform DFS only if email is not visited yet
            if (!visited.contains(accountFirstEmail)) {
                List<String> mergedAccount = new ArrayList<>();
                // Adding account name at the 0th index
                mergedAccount.add(accountName);

                DFS(mergedAccount, accountFirstEmail);
                Collections.sort(mergedAccount.subList(1, mergedAccount.size())); 
                mergedAccounts.add(mergedAccount);
            }
        }

        return mergedAccounts;
    }
}

Reference

https://leetcode.com/problems/accounts-merge/