题解 | #接头密匙#

class Solution {
#define N 2000010
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param b int整型vector<vector<>>
     * @param a int整型vector<vector<>>
     * @return int整型vector
     */
    class TireTree {
        public:
        int cnt = 1, pass[N] = {0}, tree[N][12] = {0};
        int get(char val) {
            if (val == '#') return 10;
            else if (val == '-') return 11;
            return val - '0';
        }

        void insert(string word) {
            int cur = 1;
            pass[cur]++;
            for (int i = 0; i < (int)word.size(); i++) {
                int path = get(word[i]);
                if (tree[cur][path] == 0) tree[cur][path] = ++cnt;
                cur = tree[cur][path];
                pass[cur]++;
            }
        }
        int count(string word) {
            int cur = 1;
            for (int i = 0; i < (int)word.size(); i++) {
                int path = get(word[i]);
                if (tree[cur][path] == 0) return 0;
                cur = tree[cur][path];
            }
            return pass[cur];
        }
    };


    vector<int> countConsistentKeys(vector<vector<int> >& b,
                                    vector<vector<int> >& a) {
        TireTree tire;
        vector<int> ans;
        for (int i = 0; i < a.size(); i++) {    
            string s = "";
            for (int j = 1; j < a[i].size(); j++) {
                s += to_string(a[i][j] - a[i][j - 1]) + "#";
            }
            tire.insert(s);  // 将s加入
        }
        for (int i = 0; i < b.size(); i++) {
            string s = "";
            for (int j = 1; j < b[i].size(); j++) {
                s += to_string(b[i][j] - b[i][j - 1]) + "#";
            }
            ans.push_back(tire.count(s));
        }
        return ans;
    }











};