题解 | #单双难全#

NC524 单双难全
题解一：字典树
题解思路： 构建两个字典树，一个用字符串奇数位构建，一个用字符串的全部字符创建一个字典树
图示字典树：


复杂度分析:
时间复杂度： :建树的时间复杂度由字符串长度决定，查找前缀树取决前缀长度。 建树需要遍历s字符串数组中的每个字符串，查找需要遍历t字符串数组中的每个字符串
空间复杂度： 空间复杂度最坏情况下是每个字符串都有26个英文字母

实现如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 单双难全
     * @param n int整型 字符串s的个数
     * @param s string字符串vector n个字符串s
     * @param m int整型 字符串t的个数
     * @param t string字符串vector m个字符串t
     * @return int整型vector
     */
    typedef struct tree{
        int count;
        struct tree* next[27];
        tree(int c=0,int en = 0):count(c){memset(next,0,sizeof(next));};
    }Tire;
    Tire* root_1 = new Tire();//奇数根节点
    Tire* root_2 = new Tire();
    //单数位构建
    void insert_ji(string s){
        int len = s.size();
        Tire* t = root_1;
        for(int i  = 0;i<len;i+=2){
            if(t->next[s[i]-'a']==NULL) t->next[s[i]-'a'] = new Tire();
            t = t->next[s[i]-'a'];
            t->count++;  //表明该节点所关联的单词
        }
    }
    //整个字符串建立字典树
    void insert(string s){
        int len = s.size();
        Tire* t = root_2;
        for(int i = 0;i<len;++i){
            if(t->next[s[i]-'a']==NULL) t->next[s[i]-'a'] = new Tire();
            t = t->next[s[i]-'a'];
            t->count++;
        }
    }
    //在完整字典树中查找
   int search(string s){
       int len = s.size();
       Tire* t = root_2;
       for(int i = 0;i<len;++i){
           if(t->next[s[i]-'a'] == NULL) return 0;
           t = t->next[s[i]-'a'];
       }
       return t->count;
   }
    //在查找奇数位构建字典树查找
   int search_ji(string s){
       int len = s.size();
       Tire* t = root_1;
       for(int i = 0;i<len;i+=2){
           if(t->next[s[i]-'a']==NULL) return 0;
           t = t->next[s[i]-'a'];
       }
       return t->count;
   }
    vector<int> solve(int n, vector<string>& s, int m, vector<string>& t) {
        vector<int> ans;
        for(auto it:s) {insert_ji(it); insert(it);}
        for(auto it:t) {
            if(it.size()!=1)
                ans.emplace_back(search_ji(it)-search(it));
            else ans.emplace_back(search_ji(it));
        }
        return ans;
    }
};

题解二：暴力
题解思路： 遍历两个字符串数组进行比较，判断是否是单匹配串，同时还需要判断是否是双匹配串
复杂度分析：
时间复杂度:,需要遍历两个字符串数组进行字符串的比较。
空间复杂度:,没有申请额外的空间
实现如下：

class Solution {
public:
    vector<int> solve(int n, vector<string>& s, int m, vector<string>& t) {
        vector<int> res(m, 0);
        for(int i = 0; i < m; i++){//遍历字符串数组t
            for(int j = 0; j < n; j++){ //遍历字符串数组s
                bool flag = true;
                if(t[i].length() > s[j].length())
                    continue;
                else{
                    for(int k = 0; k < t[i].length(); k++){ //查看是否是单匹配串
                        if(k % 2 == 0){ //检查奇数是否相同
                            if(t[i][k] == s[j][k])
                                continue;
                            else{
                                flag = false;
                                break;
                            }
                        }
                    }
                    if(flag){ //已经是单匹配串
                        for(int k = 0; k <t[i].length(); k++){ //检查是否是双匹配
                            if(k % 2 == 1){
                                if(t[i][k] == s[j][k])
                                    continue;
                                else{
                                    flag = false;
                                    break;
                                }
                            }
                        }
                        if(!flag || t[i].length() == 1) //当是单匹配不是双匹配或者t只有一个数时
                            res[i]++;
                    }
                }
            }
        }
        return res;
    }
};