题解 | #单双难全#

题目描述
有n个只包含小写字母的串s1,s2,..sn，每次给你一个只包含小写字母的串t。如果串S存在前缀S'，它的奇数位的字符与t的奇数位字符完全相同，称S为t的单匹配串，如果串S的偶数位字符与t的偶数位的字符全都相同，称S为t的双匹配串。
现在给你m个字符串，对于每个字符串ti，求s1,s2,...sn中有多少个串是t的单匹配串但不是t的双匹配串。

方法一：暴力解法

求解思路
对于本题的求解，我们自然想到可以用暴力循环的方法来解决。我们遍历t数组，枚举每一个s进行比较，每次比较的时候先判断是否是单匹配串，如果是再检查是否是双匹配串。如果是单匹配串不是双匹配串时，我们要把相应的结果加1.因此按照上述思路即可求出本题的答案。

图片说明

解题代码

class Solution {
public:
    vector<int> solve(int n, vector<string>& s, int m, vector<string>& t) {
        vector<int> myres(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只有一个数时
                            myres[i]++; // 并且记录结果加1
                    }
                }
            }
        }
        return myres; // 返回结果即可
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$

方法二：字典树解法--参考云影孤帆尽

求解思路
对于本问题求解，我们即是求奇数位匹配，偶数位至少有一位不同的情况，因此我们使用字典树的想法，用单匹配的数量减去奇偶完全匹配的数量，即可得到本问题的答案。

图片说明

解题代码

class Solution {
public:
    vector<int> solve(int n, vector<string>& s, int m, vector<string>& t) {
        vector<int> myres(m, 0); // 返回答案
        vector<vector<int> > dir(500000, vector<int>(26, 0)); // 字典树
        vector<int> sz(500000, 0); // 统计前缀出现次数
        int mycount = 0; // 计数
        int r1 = ++mycount, r2 = ++mycount;
        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] = ++mycount;
                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])
                    dir[p][x] = ++mycount;
                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位
                myres[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) 
                myres[i] = temp;
            else 
                myres[i] = temp - sz[p];
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：使用常数级字典树dir[常数][常数]，因此空间复杂度为 $O(1)$