C++ solution Using Trie


  • 0
    C

    Build a trie tree, with each layer corresponding to a granularity. Each tree node contains the prefix-timestamp, like "2017", "2017:01", "2017:01:02", "2017:01:02:14", etc, and granularity. The leaf tree node contains log id.

    Then

    • "put" is implemented by the adding of new nodes into the trie tree.
    • "retrieve" is implemented by the searching of the Subtrees whose root nodes 1) have the given granularity and 2) have timestamp prefix at the range of start_time prefix and end_time prefix.

    This code may be further optimized.

    class LogSystem {
    public:
    
        struct TreeNode {
            unordered_map<string, TreeNode*> children;
            string gra; // granularity
            int logid;
            bool is_leaf;
            string prefix; // prefix timestamp, like 2017:01, 2017:01:02, ..
            TreeNode() : is_leaf(false)
            {}
        };
        
        TreeNode *buildTree() {
            TreeNode *root = new TreeNode();
            return root;
        }
        
        void addNode(TreeNode *root, string &timestamp, int logid) {
            istringstream ss(timestamp);
            TreeNode *node = root; int count = 0;
            string token;
            while (getline(ss, token, ':')) {
                if (!node->children.count(token)) {
                    node->children[token] = new TreeNode();
                    node->children[token]->prefix = node->prefix + string(node->prefix.empty()?"":":") + token;
                }
                node = node->children[token];
                node->gra = gra_list[count++];
            }
            node->logid = logid;
            node->is_leaf = true;
        }
        
        vector<int> searchNode(TreeNode *root, string start_time, string end_time, string &gra) {
            istringstream ss_start(start_time);
            istringstream ss_end(end_time);
            string start_token, end_token;
            
            queue<TreeNode*> q, q_next;
            q.push(root);
            
            while (!q.empty()) {
                string token;
                getline(ss_start, token, ':'); start_token += start_token.empty() ? token : (":" + token);
                getline(ss_end, token, ':'); end_token += end_token.empty() ? token : (":" + token);
                
                bool matchGra = false;
                while (!q.empty()) {
                    TreeNode *node = q.front(); q.pop();
                    for (auto &itrpair : node->children) {
                        if (itrpair.second->prefix >= start_token && itrpair.second->prefix <= end_token) {
                            if (itrpair.second->gra == gra) {
                                matchGra = true;
                            }
                            q_next.push(itrpair.second);
                        }
                    }
                }
                swap(q, q_next);
                if (matchGra) break;
            }
            
            vector<int> res;
            while (!q.empty()) {
                TreeNode *node = q.front(); q.pop();
                if (node->is_leaf) {
                    res.push_back(node->logid);
                }
                for (auto &itrpair : node->children) {
                    q.push(itrpair.second);
                }
            }
            return res;
        }
    
        LogSystem() {
            mRoot = buildTree();
            gra_list = vector<string>{"Year", "Month", "Day", "Hour", "Minute", "Second"};
        }
        
        void put(int id, string timestamp) {
            addNode(mRoot, timestamp, id);
        }
        
        vector<int> retrieve(string s, string e, string gra) {
            vector<int> res = searchNode(mRoot, s, e, gra);
            return res;
        }
    private:
        TreeNode *mRoot;
        vector<string> gra_list;
    };
    

Log in to reply
 

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