Java DFS solution


  • 0
    //we can't use name as key
    //we need to consider the problem in another way
    //each account has an ID(0.....account.size()-1)
    //the same email address should belong to the same account/same id(we pick the smallest)   
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        List<List<String>> result = new ArrayList<List<String>>();
        Map<String, List<Integer>> groupMap = new HashMap<String, List<Integer>>();
        //Associate each email with all its account IDs
        for(int id = 0; id<accounts.size(); id++) {
             List<String> account = accounts.get(id);            
             for(int i = 1; i<account.size(); i++){ 
                 String email = account.get(i);
                 if(!groupMap.containsKey(email)) groupMap.put(email,new ArrayList<Integer>());
                 groupMap.get(email).add(id);
             }
        }
        //do DFS for each email
        Set<String> visitedEmail = new HashSet<String>();
        for(String email: groupMap.keySet()){ 
            Set<String> mergedAccount = new TreeSet<String>();
            int groupid = DFS(email, groupMap, accounts, visitedEmail, mergedAccount, new int[]{Integer.MAX_VALUE});
            if(groupid!=-1) {
                mergedAccount.add(accounts.get(groupid).get(0));//add user name
                result.add(new LinkedList<String>(mergedAccount));
            }
        }
        return result;
    }   
    //merge emails and its return account ID, which is the smallest among those IDs sharing by the emails
    public int DFS(String email, Map<String, List<Integer>> groupMap, List<List<String>> accounts, Set<String> visitedEmail, Set<String> mergedAccount, int[] finalId){
        if(visitedEmail.contains(email)) return -1;
        visitedEmail.add(email); mergedAccount.add(email);
        for(int id: groupMap.get(email)){
            finalId[0] = Math.min(finalId[0], id);
            List<String> account = accounts.get(id);
            for(int i = 1; i<account.size(); i++){                
                DFS(account.get(i), groupMap, accounts, visitedEmail, mergedAccount, finalId);
            }
        }
        return finalId[0];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.