Trie Efficient Solution

renaming_cities.cpp

#include <bits/stdc++.h>
using namespace std;

struct Node{
    bool isEndOfWord;
    int count1;
    map<char, Node *> mp;
};

Node *newNode(){
    Node *temp = new Node();
    temp->isEndOfWord = false;
    // int count1 = 0;
    return temp;
}

class TrieNode {
public:
    TrieNode *children[26];
    int freq;

    TrieNode() {
        for(int i = 0; i < 26; i++) 
            children[i] = NULL;
        freq = 0;
    }
};

// insert string in the trie and return the station code
string insert(TrieNode *root, string &s) {  
    string prefix = "";
    bool flag = false;
    TrieNode *curr = root;
    
    for(char &c : s) {
        int idx = c - 'a';
        // create new node if it doesn't exist
        if(!curr->children[idx]) {
            curr->children[idx] = new TrieNode();
            if(!flag)
                prefix += c;
            flag = true;
        }
        else 
            prefix += c;
        // move to the child node
        curr = curr->children[idx];
    }
    // increase the freq
    curr->freq++;
    // check for duplicate strings: add the suffix as the count
    if(curr->freq > 1) 
        prefix += " " + to_string(curr->freq);
    
    return prefix;
}

// arr : array of strings
// n : count of the number of strings in the array
class Solution {
public:
    void check(string *arr, int n){
        //code here
        TrieNode *root = new TrieNode();
        for(int i = 0; i < n; i++) 
            cout << insert(root, arr[i]) << endl;
    }
};




// { Driver Code Starts.
int main() {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        string arr[n];
        for(int i = 0;i<n;i++){
            string s;
            cin >> s;
            arr[i] = s;
        }
        Solution obj;
        obj.check(arr,n);
    }
    return 0;
}