异域字典

最优解法

考虑对所有X国的单词建立字典树，并且字典树上存储对应的牛客单词的下标而不是存整个单词。查询的时候直接在字典树上查询就可以了。建树时间复杂度,查询复杂度，所以总的时间复杂度为。
空间复杂度为建立字典树需要消耗的空间，为

int ch[500000][26];
int to[500000];
vector<string> solve(int n, vector<string> s,  vector<string> t, int m, vector<string> g){
    memset(ch, 0, sizeof ch);
    memset(to, -1, sizeof to);
    int cnt = 0;
    int r = ++cnt;
    assert(s.size() == n);
    assert(t.size() == n);
    assert(g.size() == m);
    for(int i = 0; i < n; ++i){
        int p = r;
        assert(s[i].size() > 0);
        for(int j = 0; j < s[i].size(); j++) {
            int x = s[i][j]-'a';
            if(!ch[p][x]) ch[p][x] = ++cnt;
            p = ch[p][x];
        }
        assert(to[p] == -1);
        to[p] = i;
    }
    vector<string > ans; ans.clear();
    for(int i = 0; i < m; ++i){
        int p = r;
        assert(g[i].size() > 0);
        for(int j = 0; j < g[i].size(); j++) {
            int x = g[i][j]-'a';
            p = ch[p][x];
            assert(p != 0);
        }
        assert(to[p] != -1);
        ans.push_back(t[to[p]]);
    }
    return ans;
}