题解 | #字典树的实现#

写到自闭。

class Solution {
public:
    /**
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */
    vector<string> trieU(vector<vector<string> >& operators) {
        if (operators.empty()) {
            return std::vector<std::string>();
        }

        std::vector<std::string> res;

        tree.push_back(new trie());

        for (int i = 0; i < operators.size(); ++i) {
            std::string op = operators[i][0];
            std::string wd = operators[i][1];

            if (op == "1") {
                trie *root = tree[0];
                for (int j = 0; j < wd.size(); ++j) {
                    if (root->word[wd[j] - 'a'] == nullptr) {
                        root->word[wd[j] - 'a'] = new trie();
                        tree.push_back(root->word[wd[j] - 'a']);
                    }
                    root = root->word[wd[j] - 'a'];
                    ++root->times;
                }
                root->end = true;
            } else if (op == "2") {
                trie *root = tree[0];
                for (int j = 0; j < wd.size(); ++j) {
                    root = root->word[wd[j] - 'a'];
                    --(root->times);
                }
                if (root->times == 0) {
                    root->end = false;
                }
            } else if (op == "3") {
                trie *root = tree[0];
                bool flag = true;
                for (int j = 0; j < wd.size(); ++j) {
                    if (root->word[wd[j] - 'a']) {
                        root = root->word[wd[j] - 'a'];
                    } else {
                        flag = false;
                        break;
                    }
                }
                if (root->end && flag) {
                    res.push_back("YES");
                } else {
                    res.push_back("NO");
                }
            } else {
                trie *root = tree[0];
                int num = 0;
                int flag = true;
                for (int j = 0; j < wd.size(); ++j) {
                    if (root->word[wd[j] - 'a']) {
                        root = root->word[wd[j] - 'a'];
                    } else {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    num = root->times;
                }
                res.push_back(std::to_string(num));
            }
        }

        for (auto &it : tree) {
            delete(it);
        }

        return res;
    }

private:
  struct trie {
      bool end;
      int times;
      std::vector<trie *> word;
      trie() : end(false), word(std::vector<trie *>(26, nullptr)), times(0) {}
  };

  std::vector<trie *> tree;
};