Simple Java solution using HashMap


  • 1
    A
    public class Solution {
        public List<List<String>> findDuplicate(String[] paths) {
            List<List<String>> list = new ArrayList<List<String>>();
            
            HashMap<String,List<String>> map = new HashMap<>();
            
            int l = paths.length;
            
            for(int i=0;i<l;i++){
                String s = paths[i];
                StringBuilder sb = new StringBuilder("");
                char[] stc = s.toCharArray();
                int m = s.length();
                int j = 0;
                while(stc[j] != ' '){
                    sb.append(stc[j++]);
                }
                String path = sb.toString();
                sb.setLength(0);
                j++;
                String res = "";
                String name = "";
                while(j < m){
                    if(stc[j] == ' '){
                        res = "";
                        name = "";
                    }else if(stc[j] == '('){
                        name = path + '/' + res;
                        res = "";
                    }else if(stc[j] == ')'){
                        if(map.containsKey(res)){
                            List<String> slist = map.get(res);
                            slist.add(name);
                            map.put(res,slist);
                        }else{
                            List<String> slist = new ArrayList<String>();
                            slist.add(name);
                            map.put(res,slist);
                        }
                    }else{
                        res += stc[j];
                    }
                    j++;
                }
            }
            for(String s : map.keySet()){
                List<String> slist = map.get(s);
                if(slist.size() > 1){
                    list.add(slist);
                }
            }
            
            return list;
        }
    }
    

  • 0
    A

    @ashish53v Helped me out, especially when I was timing out on last 2 test cases... thanks a bunch!


  • 0
    A

    @aboulmagd I just ran the code and it was accepted. Sometimes same code gets TLE for no reason. Try to submit it again, it should work.


  • 0
    A

    @aboulmagd Also check out my this solution, this is much cleaner and easier to understand

    class Solution {
        public List<List<String>> findDuplicate(String[] paths) {
            List<List<String>> list = new ArrayList<>();
            int l = paths.length;
            
            if(l == 0)
                return list;
            
            Map<String,List<String>> map = new HashMap<>();
            
            for(String str:paths){
                String[] parts = str.split(" ");
                String main = parts[0];
                
                for(int i=1;i<parts.length;i++){
                    String curr = parts[i];
                    String[] split = curr.split("\\(");
                    String content = split[1].substring(0,split[1].length()-1);
                    
                    String path = main + "/" + split[0];
                    
                    List<String> slist = map.getOrDefault(content,new ArrayList<String>());
                    
                    //System.out.println(content + " content ");
                    
                    slist.add(path);
                    
                    map.put(content,slist);
                        
                }
            }
            
            for(String key:map.keySet()){
                List<String> slist = map.get(key);
                //System.out.println(key + " keylll " + slist.size());
                if(slist.size() > 1)
                list.add(slist);
            }
            
            
            return list;
        }
    }
    

Log in to reply
 

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