题解 | #单双难全#

思路：

题目的主要信息：

• 字符串t与字符串s的前缀（从头开始，取前t.length个），若是二者所有的奇数位字符串都相等则称之为单匹配，若是二者所有偶数位字符串都相等，则称之为双匹配
• 奇数偶数下标从1开始，注意与字符串下标之间的关系
• 需要求m个t字符串，各自在n个s字符串中有多少属于单匹配但不属于双匹配，前者是一个完全匹配，后者是一个不完全不匹配（注：不是完全不匹配）
• 输入只有小写字母

方法一：暴力法
具体做法：
遍历t数组，枚举每一个s进行比较。
每次比较的时候先判断是否是单匹配串，如果是再检查是否是双匹配串，如果不是再把相应的结果加1。
需要注意的是t只有一个字符的情况，双匹配匹配不到，会算作是双匹配而无法计算，需要单独讨论。

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;
    }
};

复杂度分析：

• 时间复杂度：，表示每个字符串t的长度，外面两层遍历，内部是遍历每个字符串t
• 空间复杂度：，常数个空间

方法二：字典树
具体做法：
因为我们要找的是完全奇数位匹配且不完全偶数位不匹配，即奇数位必须完全相同，偶数位至少有一位不同。因此我们可以考虑用单匹配的数量减去奇偶完全匹配的数量。
依照这个原理，我们建立两棵字典树：对所有的奇数位置组成的串建立一颗字典树，再对所有完整的建立字典树，同时在字典树上插入的时候顺便记录每个前缀出现次数。后续我们只需要遍历每个字符串，在第一个字典树上查询，再在第二个字典树上查询，单数匹配个数-全匹配个数就是所求答案。

和方法一类似，要注意t字符串只有1位的情况。

class Solution {
public:
    vector<int> solve(int n, vector<string>& s, int m, vector<string>& t) {
        vector<int> res(m, 0); //返回答案
        vector<vector<int> > dir(500000, vector<int>(26, 0)); //字典树
        vector<int> sz(500000, 0); //统计前缀出现次数
        int count = 0; //计数
        int r1 = ++count, r2 = ++count;
        for(int i = 0; i < n; i++){
            int p = r1;
            for(int j = 0; j < s[i].size(); j+=2){//奇数位的字典树
                int x = s[i][j] - 'a';
                if(!dir[p][x])
                    dir[p][x] = ++count;
                sz[p]++;
                p = dir[p][x];
            }
            sz[p]++;
            p = r2;
            for(int j = 0; j < s[i].size(); j++){//全部位字典树
                int x = s[i][j] - 'a';
                if(!dir[p][x]){
                    count++;
                    dir[p][x] = count;
                }
                sz[p]++;
                p = dir[p][x];
            }
            sz[p]++;
        }
        for(int i = 0; i < m; i++){ //遍历每个t
            int temp;
            int p = r1;
            for(int j = 0; j < t[i].size(); j+=2){
                int x = t[i][j] - 'a';
                if(!dir[p][x]){  //不是单匹配
                    p = -1;
                    break;
                }
                p = dir[p][x];
            }
            if(p == -1)
                continue;
            if(t[i].size() == 1){ //t字符串只有1位
                res[i] = sz[p];
                continue;
            }
            temp = sz[p];
            p = r2;
            for(int j = 0; j < t[i].size(); j++){
                int x = t[i][j] - 'a';
                if(!dir[p][x]){ //不是全匹配
                    p = -1;
                    break;
                }
                p = dir[p][x];
            }
            if(p == -1)
                res[i] = temp;
            else
                res[i] = temp - sz[p];
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，建树相当于遍历每个s字符串的每个字符，查询相当于遍历每个t字符串的每个字符
• 空间复杂度：，字典树最大可达到这个程度