Java Solution (Build graph + DFS search)


  • 12

    I have tried my best to make my code clean. Hope the basic idea below may help you. Happy coding!

    Basicly, this is a graph problem. Notice that each account[ i ] tells us some edges. What we have to do is as follows:

    1. Use these edges to build some components. Common email addresses are like the intersections that connect each single component for each account.
    2. Because each component represents a merged account, do DFS search for each components and add into a list. Before add the name into this list, sort the emails. Then add name string into it.

    Examples: Assume we have three accounts, we connect them like this in order to use DFS.
    {Name, 1, 2, 3} => Name -- 1 -- 2 -- 3
    {Name, 2, 4, 5} => Name -- 2 -- 4 -- 5 (The same graph node 2 appears)
    {Name, 6, 7, 8} => Name -- 6 -- 7 -- 8
    (Where numbers represent email addresses).

    class Solution {
        public List<List<String>> accountsMerge(List<List<String>> accounts) {
            List<List<String>> res = new ArrayList<>();
            Map<String, Node> map = new HashMap<>();    // <Email, email node>  
                    
            // Build the graph;
            for (List<String> list : accounts) {
                for (int j = 1; j < list.size(); j++) {
                    String email = list.get(j);
                    
                    if (!map.containsKey(email)) {
                        Node node = new Node(email, list.get(0));
                        map.put(email, node);
                    }
                    
                    if (j == 1) continue;
                    //Connect the current email node to the previous email node;
                    map.get(list.get(j - 1)).neighbors.add(map.get(email));
                    map.get(email).neighbors.add(map.get(list.get(j - 1)));
                }
            }
            
            // DFS search for each components(each account);
            Set<String> visited = new HashSet<>();
            for (String s : map.keySet()) {
                if (visited.add(s)) {
                    List<String> list = new LinkedList<>();
                    list.add(s);              
                    dfs(map.get(s), visited, list);
                    Collections.sort(list);
                    list.add(0, map.get(s).username);
                    res.add(list);
                }
            }        
            return res;
        }
        
        public void dfs(Node root, Set<String> visited, List<String> list) {
            for (Node node : root.neighbors) {
                if (visited.add(node.val)) {
                    list.add(node.val);
                    dfs(node, visited, list);
                }
            }
        }
        
        class Node {
            String val;         // Email address;
            String username;    // Username;
            List<Node> neighbors;
            Node(String val, String username) {
                this.val = val;
                this.username = username;
                neighbors = new ArrayList<>();
            }
        }
    }
    

    Please check the clean version posted by @zhangchunli below. Thanks for updating.


  • 5
    M

    @FLAGbigoffer
    Thanks for sharing your idea.
    My code is based on your idea, but actually we don't need an additional "Node" class.

    class Solution {
        public List<List<String>> accountsMerge(List<List<String>> accounts) {
            List<List<String>> result = new ArrayList<>();
            if(accounts==null || accounts.size()==0)
                return result;
            
            Map<String, String> names = new HashMap<String, String>(); //email - username
            Map<String, Set<String>> map = new HashMap<String, Set<String>>(); //email - neighbors
            Set<String> emails = new HashSet<String>(); 
            
            for(List<String> list : accounts){
                String name = list.get(0);
                for(int i=1; i<list.size(); i++){
                    String email = list.get(i);
                    emails.add( email ); 
                    names.put( email, name );
                    map.putIfAbsent( email, new HashSet<String>() );
                    
                    if(i==1)
                        continue;
                    
                    //build the "edge" between two adjacent email-nodes
                    map.get( list.get(i-1) ).add( email );
                    map.get( email ).add( list.get(i-1) );
                }
            }
            
            Set<String> visited = new HashSet<String>();
            for(String s : emails)
                if( !visited.contains(s) ){
                    visited.add(s);
                    List<String> buffer = new ArrayList<String>();
                    buffer.add(s);
                    helper(s, map, visited, buffer);
                    Collections.sort(buffer);
                    buffer.add(0, names.get(s));
                    result.add(buffer);
                }
            return result; 
        }
        
        private void helper(String s, Map<String, Set<String>> map, Set<String> visited, List<String> buffer){
            for(String node : map.get(s))
                if( !visited.contains(node) ){
                    visited.add(node);
                    buffer.add(node);
                    helper(node, map, visited, buffer);
                }
        }
    }
    

  • 0

    @mycoy Good job! The code is cleaner right now. Thanks for updating.


  • 5
    Z

    @mycoy Thanks for sharing. It seems that names and emails are also not necessary. Here is my modified code:

    class Solution {
        public List<List<String>> accountsMerge(List<List<String>> accounts) {
            // build the graph
            Map<String,Set<String>> graph=new HashMap<>();
            for(List<String> ls:accounts){
                for(int i=1;i<ls.size();i++){
                    if(!graph.containsKey(ls.get(i))) graph.put(ls.get(i),new HashSet<String>());
                    graph.get(ls.get(i)).add(ls.get(1));
                    graph.get(ls.get(1)).add(ls.get(i));
                }
            }
            // traverse the graph, find out all the connected subgraph
            Set<String> visited=new HashSet<>();
            List<List<String>> result=new ArrayList<>();
            for(List<String> ls:accounts){
                    if(!visited.contains(ls.get(1))){
                        List<String> ans=new ArrayList<>();
                        bfs(graph,visited,ls.get(1),ans); // or dfs(graph,visited,ls.get(1),ans)
                        Collections.sort(ans);
                        ans.add(0,ls.get(0));
                        result.add(ans);
                    }
            }
            return result;
        }
        public void dfs(Map<String,Set<String>> graph, Set<String> visited, String s,List<String> ans){
            ans.add(s);
            visited.add(s);
            for(String str:graph.get(s)){
                if(!visited.contains(str)){
                    dfs(graph,visited,str,ans);
                }
            }
        }
        public void bfs(Map<String,Set<String>> graph, Set<String> visited, String s,List<String> ans){
            Queue<String> q=new LinkedList<>();
            q.add(s);
            visited.add(s);
            while(!q.isEmpty()){
                String t=q.poll();
                ans.add(t);
                for(String str:graph.get(t)){
                    if(!visited.contains(str)){
                        q.add(str);
                        visited.add(str);
                    } 
                }
            }
        }
    }
    

    Thanks for the comment. @FLAGbigoffer


  • 0

    @zhangchunli Here we go! It's clean code right now! Thanks for updating.


  • 0

    @zhangchunli A quick note is for each component, you always connected other nodes to the first node, which makes the graph doesn't go deeply too much but goes broad. In this case, I think BFS is a better choice instead of DFS. That's fine. Great job! Upvoted!


  • 0
    Z

    @FLAGbigoffer Yes, you are right. I have added BFS method.


  • 0

    My DFS version:

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
            if (accounts == null || accounts.isEmpty()) {
                return new ArrayList<>();
            }
            
            Map<String, List<Integer>> emailMap = new HashMap<>();
            for (int i = 0; i < accounts.size(); i++) {
                List<String> emails = accounts.get(i);
                for (int j = 1; j < emails.size(); j++) {
                    String email = emails.get(j);
                    if (!emailMap.containsKey(email)) {
                        emailMap.put(email, new ArrayList<>());
                    }
                    emailMap.get(email).add(i);
                }
            }
            
            Set<String> visited = new HashSet<>();
            List<List<String>> ret = new ArrayList<>();
            for (String email : emailMap.keySet()) {
                List<String> emails = dfs(accounts, emailMap, email, visited);
                if (emails != null) {
                    Collections.sort(emails);
                    emails.add(0, accounts.get(emailMap.get(email).get(0)).get(0));
                    ret.add(emails);
                }
            }
            return ret;
        }
        
        private List<String> dfs(
            List<List<String>> accounts,
            Map<String, List<Integer>> emailMap,
            String email,
            Set<String> visited) {
            if (visited.contains(email)) {
                return null;
            }
            
            List<String> ret = new ArrayList<>();
            ret.add(email);
            visited.add(email);
            for (Integer index : emailMap.get(email)) {
                for (int i = 1; i < accounts.get(index).size(); i++) {
                    String siblingEmail = accounts.get(index).get(i);
                    if (!siblingEmail.equals(email)) {
                        List<String> emails = dfs(accounts, emailMap, siblingEmail, visited);
                        if (emails != null) {
                            ret.addAll(emails);
                        }
                    }
                }
            }
            return ret;
        } 
    

Log in to reply
 

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