Java Solution, HashMap


  • 7
    public class Solution {
        public List<List<String>> findDuplicate(String[] paths) {
            List<List<String>> result = new ArrayList<List<String>>();
            int n = paths.length;
            if (n == 0) return result;
            
            Map<String, Set<String>> map = new HashMap<>();
            for (String path : paths) {
                String[] strs = path.split("\\s+");
                for (int i = 1; i < strs.length; i++) {
                    int idx = strs[i].indexOf("(");
                    String content = strs[i].substring(idx);
                    String filename = strs[0] + "/" + strs[i].substring(0, idx);
                    Set<String> filenames = map.getOrDefault(content, new HashSet<String>());
                    filenames.add(filename);
                    map.put(content, filenames);
                }
            }
            
            for (String key : map.keySet()) {
                if (map.get(key).size() > 1) {
                    result.add(new ArrayList<String>(map.get(key)));
                }
            }
            
            return result;
        }
    }
    

  • 0
    M

    I use List<String> instead of Set<String>, but it doesn't work. I think it probably is caused by duplicate directory. However, I didn't derive this information from the question. And I tried use duplicate directory in the input String array and the OJ is fine with it. Could anyone clarify it for me? Thx!

    public class Solution {
        public List<List<String>> findDuplicate(String[] paths) {
            List<List<String>> output = new ArrayList<List<String>>();
            Map<String, List<String>> hashmap = new HashMap<String, List<String>>();
            if (paths.length == 0) return output;
            for (int i = 0; i < paths.length; i++) {
                String tmp = paths[i];
                String[] curr = tmp.split(" ");
                for (int j = 1; j < curr.length; j++) {
                    String[] contents = curr[j].split("txt");
                    String dit = curr[0] + "/" + contents[0] + "txt";
                    List<String> dits = hashmap.getOrDefault(contents[1], new ArrayList<String>());
                    dits.add(dit);
                    hashmap.put(contents[1], dits);
                }
            }
            for (String key : hashmap.keySet()) {
                if (hashmap.get(key).size() > 1) {
                    output.add(hashmap.get(key));
                }
            }
            return output;
        }
    }
    

  • 0
    A

    @MutouMan said in Java Solution, HashMap:

    > public class Solution {
    >     public List<List<String>> findDuplicate(String[] paths) {
    >         List<List<String>> output = new ArrayList<List<String>>();
    >         Map<String, List<String>> hashmap = new HashMap<String, List<String>>();
    >         if (paths.length == 0) return output;
    >         for (int i = 0; i < paths.length; i++) {
    >             String tmp = paths[i];
    >             String[] curr = tmp.split(" ");
    >             for (int j = 1; j < curr.length; j++) {
    >                 String[] contents = curr[j].split("txt");
    >                 String dit = curr[0] + "/" + contents[0] + "txt";
    >                 List<String> dits = hashmap.getOrDefault(contents[1], new ArrayList<String>());
    >                 dits.add(dit);
    >                 hashmap.put(contents[1], dits);
    >             }
    >         }
    >         for (String key : hashmap.keySet()) {
    >             if (hashmap.get(key).size() > 1) {
    >                 output.add(hashmap.get(key));
    >             }
    >         }
    >         return output;
    >     }
    > }
    

    Hi, I think your code is wrong because you use "txt" to split the file name and the content. It is better to use "(" instead of "txt" as the filename may contain txt as a substring.
    It is totally fine to use List<String> as each file name (+ directory of course) should be unique by the problem description.

    For the actual test case provided by OJ, look at this example:
    ["root/qgjazhtliq/djmevsktisuvd/acsuolhnermqzok/mkts/ibrdqxawjgut/emb wl.txt(odumfqzwczehoyk) z.txt(gojsklotgchjzfm) txtoyg.txt(gojsklotgchjzfm) eupidhefx.txt(ahlsazuzrsf) rekzkaifwp.txt(yfxaymkefaofowqjpgaceffkjsehtmqkgy) l.txt(odumfqzwczehoyk) bqmhpxumxlbe.txt(yfxaymkefaofowqjpgaceffkjsehtmqkgy) qoqgiauqbayuc.txt(odumfqzwczehoyk) mpstemqlxy.txt(ahlsazuzrsf)"]

    The bolded file cause the problem.


  • 0
    G

    The similar idea but no substring and set.

    public List<List<String>> findDuplicate(String[] paths) {
        Map<String, List<String>> map = new HashMap<>();
        List<List<String>> res = new ArrayList<>();
        for (String p : paths) {
          String[] splits = p.split("\\s");
          String root = null;
          for (String s : splits) {
            if (root == null) root = s;
            else {
              String[] file = s.split("[\\(\\)]");
              if (!map.containsKey(file[1])) {
                map.put(file[1], new ArrayList<>());
              }
              map.get(file[1]).add(root + "/" + file[0]);
            }
          }
        }
        for (List<String> r : map.values()) {
          if (r.size() > 1)
            res.add(r);
        }
        return res;
      }
    

Log in to reply
 

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