题解 | #接头密匙#
接头密匙
https://www.nowcoder.com/practice/c552d3b4dfda49ccb883a6371d9a6932
class Solution { private: int son[100010][10], idx; int ed[100010], st[100010]; public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param b int整型vector<vector<>> * @param a int整型vector<vector<>> * @return int整型vector */ void insert(vector<int>& s) { int p = 0; int len = s.size(); for (int i = 0; i + 1 < len; i ++ ) { int x = s[i + 1] - s[i]; // 差分插入 Trie 树 if (!son[p][x]) son[p][x] = ++ idx; // 创建子节点 p = son[p][x]; st[p] ++; // 记录经过当前p节点的字符串数量 } ed[p] ++; // 记录以p为叶子节点的字符串的数量 } int query(vector<int>& s) { int p = 0; int len = s.size(); for (int i = 0; i + 1 < len; i ++ ) { int x = s[i + 1] - s[i]; if (!son[p][x]) return 0; p = son[p][x]; } return st[p]; } vector<int> countConsistentKeys(vector<vector<int> >& b, vector<vector<int> >& a) { // write code here vector<int> ans; int m = b.size(), n = a.size(); for (int i = 0; i < n; i ++ ) insert(a[i]); // 插入a的每个串 for (int i = 0; i < m; i ++ ) ans.push_back(query(b[i])); // 查询b的每个串 return ans; } };