Advertisement
jibha

Untitled

May 24th, 2022
598
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.    
  4.     struct trie{
  5.         unordered_map<string,struct trie*> children;
  6.         bool isEnd;
  7.     };
  8.    
  9.     struct trie* getNode(){
  10.         struct trie* node=new trie;
  11.         node->children.clear();
  12.         node->isEnd=false;
  13.         return node;
  14.     }
  15.    
  16.    
  17.     void insert(struct trie* root,vector<string>& v){
  18.        
  19.         struct trie* ptr=root;
  20.        
  21.         for(int i=0;i<v.size();i++){
  22.             if(ptr->children.count(v[i])){
  23.                 ptr->children[v[i]]=getNode();
  24.                 ptr=ptr->children[v[i]];
  25.             }
  26.             ptr=ptr->children[v[i]];
  27.         }
  28.        
  29.         ptr->isEnd=true;
  30.     }
  31.    
  32.     bool isSame(struct trie* node1,struct trie* node2){
  33.        
  34.        
  35.        
  36.         if((node1->children.size()==0)&&(node2->children.size()==0)&&(node1->isEnd==node2->isEnd)){
  37.             return true;
  38.         }
  39.        
  40.         if(node1->children.size()!=node2->children.size()){
  41.             return false;
  42.         }
  43.        
  44.         bool ans=true;
  45.        
  46.         for(auto iter:node1->children){
  47.             if(node2->children.count(iter.first)==0){
  48.                 return false;
  49.             }else{
  50.                 ans=ans&isSame(iter.second,node2->children[iter.first]);
  51.             }
  52.         }
  53.        
  54.         return ans;
  55.     }
  56.    
  57.     vector<vector<string>> all(struct trie* root){
  58.         for(auto iter:root->children){
  59.             cout<<iter.first<<' ';
  60.             all(iter.second);
  61.         }
  62.         return {};
  63.     }
  64.    
  65.    
  66.     vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {
  67.         struct trie* root=getNode();
  68.         vector<vector<string>> ans;
  69.        
  70.         for(auto iter:paths){
  71.             insert(root,iter);
  72.         }
  73.        
  74.         all(root);
  75.        
  76.         return ans;
  77.     }
  78. };
Advertisement
RAW Paste Data Copied
Advertisement