NC524 單雙難全
題解一：字典樹
題解思路： 構(gòu)建兩個(gè)字典樹，一個(gè)用字符串奇數(shù)位構(gòu)建，一個(gè)用字符串的全部字符創(chuàng)建一個(gè)字典樹
圖示字典樹：


復(fù)雜度分析:
時(shí)間復(fù)雜度： :建樹的時(shí)間復(fù)雜度由字符串長(zhǎng)度決定，查找前綴樹取決前綴長(zhǎng)度。 建樹需要遍歷s字符串?dāng)?shù)組中的每個(gè)字符串，查找需要遍歷t字符串?dāng)?shù)組中的每個(gè)字符串
空間復(fù)雜度： 空間復(fù)雜度最壞情況下是每個(gè)字符串都有26個(gè)英文字母

實(shí)現(xiàn)如下：

class Solution {
public:
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可
     *
     * 單雙難全
     * @param n int整型 字符串s的個(gè)數(shù)
     * @param s string字符串vector n個(gè)字符串s
     * @param m int整型 字符串t的個(gè)數(shù)
     * @param t string字符串vector m個(gè)字符串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();//奇數(shù)根節(jié)點(diǎn)
    Tire* root_2 = new Tire();
    //單數(shù)位構(gòu)建
    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++;  //表明該節(jié)點(diǎn)所關(guān)聯(lián)的單詞
        }
    }
    //整個(gè)字符串建立字典樹
    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;
   }
    //在查找奇數(shù)位構(gòu)建字典樹查找
   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;
    }
};

題解二：暴力
題解思路： 遍歷兩個(gè)字符串?dāng)?shù)組進(jìn)行比較，判斷是否是單匹配串，同時(shí)還需要判斷是否是雙匹配串
復(fù)雜度分析：
時(shí)間復(fù)雜度:,需要遍歷兩個(gè)字符串?dāng)?shù)組進(jìn)行字符串的比較。
空間復(fù)雜度:,沒有申請(qǐng)額外的空間
實(shí)現(xiàn)如下：

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++){//遍歷字符串?dāng)?shù)組t
            for(int j = 0; j < n; j++){ //遍歷字符串?dāng)?shù)組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){ //檢查奇數(shù)是否相同
                            if(t[i][k] == s[j][k])
                                continue;
                            else{
                                flag = false;
                                break;
                            }
                        }
                    }
                    if(flag){ //已經(jīng)是單匹配串
                        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) //當(dāng)是單匹配不是雙匹配或者t只有一個(gè)數(shù)時(shí)
                            res[i]++;
                    }
                }
            }
        }
        return res;
    }
};