题解 | #单双难全#

算法思想一：暴力法

解题思路：

遍历t数组，枚举每一个s进行比较。

依次遍历 t 取出元素 it， 再取出 s 中元素 is :

通过 去除 s 中非 it 单匹配串的字符串， 再比较 ，去除满足双匹配的字符串。

在统计剩余字符串中满足单匹配串的个数。

图解：

代码展示：

Python版本

class Solution:
    def solve(self , n , s , m , t ):
        # write code here
        # 返回数组
        res = []
        for it in t:
            # 获取ti的奇数位字符
            temp_it = self.get_single_str(it)
            # 分别计算 temp_it 长度，ti 的长度
            check_len = len(temp_it)
            tStr_len = len(it)
            print(temp_it)
            # 判断字符串 s 中有几个与ti 是单匹配串
            temp = [self.get_single_str(i)[:check_len] for i in s
                    if (i[:tStr_len] != it if tStr_len > 1 else True) and i[0] == it[0]]
            # 计算有几个属于单匹配串
            res.append(temp.count(temp_it))
        return res
    # 找到 s 串的奇数位字符
    def get_single_str(self, s: str):
        return ''.join([s[i] for i in range(len(s)) if i % 2 == 0])

复杂度分析

时间复杂度：其中 表示所有 ti 的长度，两个数组的遍历再加 t 数组的 ti 的遍历

空间复杂度：仅使用常数级变量空间

算法思想二：字典树

解题思路：

对所有单数位置组成的串建立一颗字典树，再对所有完整的建立字典树.在字典树上插入的时候顺便记录每个前缀出现次数。
那么查询的时候只要在单数位置组成的字典树上查一下，完整字典树上查一下，单数成功匹配的个数-完整匹配的个数就是答案。注意要特判的情况。

代码展示：

C++版本

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
     */
    int ch[500000][26];
    int sz[500000];
    vector solve(int n, vector<string>& s, int m, vector<string>& t) {
        // write code here
        memset(ch, 0, sizeof ch);
        memset(sz, 0, sizeof sz);
        int cnt = 0;
        int r1 = ++cnt, r2 = ++cnt;
        assert(s.size() == n);
        assert(t.size() == m);
        for(int i = 0; i < n; ++i){
            int p = r1;
            assert(s[i].size() > 0);
            for(int j = 0; j < s[i].size(); j+=2) {//奇数位的字典树
                int x = s[i][j]-'a';
                if(!ch[p][x]) ch[p][x] = ++cnt;
                sz[p]++;
                p = ch[p][x];
            }
            sz[p]++;
            p = r2;
            for(int j = 0; j < s[i].size(); ++j){//全部位字典树
                int x = s[i][j]-'a';
                if(!ch[p][x]) ch[p][x] = ++cnt;
                sz[p]++;
                p = ch[p][x];
            }
            sz[p]++;
        }
        vector ans; ans.clear();
        for(int i = 0; i < m; ++i){
            assert(t[i].size() > 0);
            int temp;
            int p = r1;
            for(int j = 0; j < t[i].size(); j += 2){
                int x = t[i][j]-'a';
                if(!ch[p][x]) {p = -1; break;}
                p = ch[p][x];
            }
            if(p == -1) {ans.push_back(0); continue;}
            if(t[i].size() == 1){ans.push_back(sz[p]); continue;}
            temp = sz[p];
            p = r2;
            for(int j = 0; j < t[i].size(); j ++){
                int x = t[i][j]-'a';
                if(!ch[p][x]) {p = -1; break;}
                p = ch[p][x];
            }
            if(p == -1)ans.push_back(temp);
            else ans.push_back(temp-sz[p]);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：其中 表示所有 ti 的长度，其中 表示所有 si 的长度，分别对 s t 的遍历及对si ti的遍历时间

空间复杂度：仅使用常数级变量空间