Advertisement
Guest User

Untitled

a guest
Mar 9th, 2022
128
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.    
  3.     class TrieNode {
  4.         String name;
  5.         String hashValue;
  6.         Map<String, TrieNode> childNodes;
  7.        
  8.         TrieNode() {
  9.             childNodes = new HashMap<>();
  10.         };
  11.        
  12.         TrieNode(String name) {
  13.             childNodes = new HashMap<>();
  14.             this.name = name;
  15.         }
  16.        
  17.         public void insert(List<String> path) {
  18.             TrieNode cur = this;
  19.             for(String node : path){
  20.                 if(!cur.childNodes.containsKey(node)){
  21.                     cur.childNodes.put(node, new TrieNode(node));
  22.                 }
  23.                 cur = cur.childNodes.get(node);
  24.             }
  25.         }
  26.     }
  27.    
  28.     public void serialize(TrieNode root, Map<String,Integer> pathsMap) {
  29.         if(root.childNodes.isEmpty()) {
  30.             return;
  31.         }
  32.         StringBuilder sb = new StringBuilder();
  33.        
  34.         List<String> childNodes = new ArrayList<>(root.childNodes.keySet());
  35.         Collections.sort(childNodes);
  36.        
  37.         for(String childName : childNodes) {
  38.             TrieNode childTrie = root.childNodes.get(childName);
  39.             sb.append("(");
  40.             serialize(childTrie, pathsMap);
  41.             sb.append(childName);
  42.             if(!childTrie.childNodes.isEmpty()) sb.append(",").append(childTrie.hashValue);
  43.         }
  44.         root.hashValue = sb.append(")").toString();
  45.         pathsMap.put(root.hashValue, pathsMap.getOrDefault(root.hashValue, 0) + 1);
  46.     }
  47.    
  48.     public void deleteDuplicateNode(TrieNode root, Map<String,Integer> pathsMap) {
  49.         if(root.childNodes.isEmpty())
  50.             return;
  51.        
  52.         List<String> childNodes = new ArrayList<>(root.childNodes.keySet());
  53.         Collections.sort(childNodes);
  54.        
  55.         for(String childName : childNodes){
  56.             TrieNode childNode = root.childNodes.get(childName);
  57.             deleteDuplicateNode(childNode, pathsMap);
  58.             if(pathsMap.containsKey(childNode.hashValue) && pathsMap.get(childNode.hashValue) > 1) {
  59.                 root.childNodes.remove(childName);
  60.             }
  61.         }
  62.     }
  63.    
  64.     public void generateResult(TrieNode root, List<String> list, List<List<String>> result) {
  65.         if(!list.isEmpty()) {
  66.             result.add(new ArrayList<>(list));
  67.         }
  68.        
  69.         for(String childName : root.childNodes.keySet()) {
  70.             list.add(childName);
  71.             TrieNode childNode = root.childNodes.get(childName);
  72.             generateResult(childNode, list, result);
  73.             list.remove(list.size() - 1);
  74.         }
  75.     }
  76.    
  77.     public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {
  78.        
  79.         // Xay dung cay Trie
  80.         TrieNode root = new TrieNode();
  81.         for(List<String> path : paths){
  82.             root.insert(path);
  83.         }
  84.        
  85.         // Tinh gia tri bam cua tung nut trong cay va luu vao pathsMap
  86.         Map<String,Integer> pathsMap = new HashMap<>();
  87.         serialize(root, pathsMap);
  88.        
  89.         // Xoa cac cay thu muc con trung lap
  90.         deleteDuplicateNode(root, pathsMap);
  91.        
  92.         // Tao mang ket qua
  93.         List<List<String>> result = new ArrayList<>();
  94.         generateResult(root, new ArrayList<>(), result);
  95.        
  96.         return result;
  97.     }
  98. }
Advertisement
RAW Paste Data Copied
Advertisement