有n个只包含小写字母的串s1,s2,..sn，每次给你一个只包含小写字母的串t。如果串S存在前缀S'，它的奇数位的字符与t的奇数位字符完全相同，称S为t的单匹配串，如果串S的偶数位字符与t的偶数位的字符全都相同，称S为t的双匹配串。
现在给你m个字符串，对于每个字符串t，求s1,s2,...sn中有多少个串是t的单匹配串但不是t的双匹配串。
示例1
复制
3,["abc", "bbc", "cbd"],3,["abc","cad","bac"]复制
[0,1,1]对于字符串"abc"。没有满足条件的单匹配串
字符串“cad"有满足条件的串: "cbd" ,第一个位置都是c，第三个位置都是d，是单匹配串，但是第二个位置不同，不是双匹配串
字符串"bac"有满足条件的串: "bbc" ,第一个位置都是b，第三个位置都是c，是单匹配串，但是第二个位置不同，不是双匹配串
【思路】
针对前缀数量统计问题，通常采取字典树trie解决。
字典树每个节点包含一个 next[26]数组 其中next[k]指向 第k个字符所在的节点位置（可能采取指针勾连，也可能是数组下标）
字典树主要操作：
插入一个word 从根节点开始，依次取出每个字符，沿着路径。若没有该方向延升，那么新建节点，同时路途上的点pre++ ,即 前缀数量++删除一个word 从根节点开始，依次取出每个字符，沿着路径搜索，到达word最后一个字符所在节点时，所在sum--查询以某个word为前缀的单词数量，从根节点开始沿着路径，到达word最后一个字符所在的节点，取出pre
本题要求，在字典中满足，和t的奇数位匹配，但不和t的偶数位匹配的单词数量。
基本思路，构建两颗字典树
其中一棵树插入每个完整单词S另外一棵树插入每个单词S的奇数位组成的单词。那么对于一个单词t 通过查询：
在奇数位单词组成的字典树中的前缀匹配数量为：a在完整单词组成的字典树中的前缀匹配数量为 ： b那么可以知道： a>=b
完整匹配=奇数位匹配+偶数位匹配
因为一个单词t若是能在完整单词字典树中有前缀匹配（那么对应奇数位一定匹配） 那么在奇数位单词字典树中一定有对应的前缀匹配，因此 满足奇数位前缀匹配 同时 偶数位前缀不匹配 的总数为: a-b
class trie //字典树 { private: int next[100000][26]={0};//其中next[i][j]=k 表示字典树i节点的第j条走向的点 指向k int sum[500000]={0};//sum[i]=k 表示以i节点为末尾的 单词出现的数量 int pre[500000]={0};//pre[i]=k 表示以i节点之前路径 为前缀的单词数量 int num=1;//表示节点的数量 public: void add_word(string word) //插入一个单词 { int p=0; for(int i=0;i<word.size();i++) { int c=word[i]-'a';//偏移量 if(next[p][c]==0) //该条路径还没有创建 { next[p][c]=num; num++; } p=next[p][c]; pre[p]++;//中间经过的点pre++ } sum[p]++;//最终点的sum++ } int pre_fun(string word) //判断释放有以word为前缀的 { int p=0; for(int i=0;i<word.size();i++) { int c=word[i]-'a';//偏移 if(next[p][c]==0) //那么无需删除 { return 0; } p=next[p][c]; if(pre[p]==0) return 0; } if(pre[p]>0) //最终到达该前缀单词末尾 并且 数量大于0 return pre[p]; else return 0; } }; 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 */ vector<int> solve(int n, vector<string>& s, int m, vector<string>& t) { trie trie1; //只插入 每个单词奇数位组合而成的单词 trie trie2; //插入 每个完整单词 for(int i=0;i<n;i++) { string word1,word2; for(int j=0;j<s[i].size();j++) { if(j%2==0) word1+=s[i][j]; word2+=s[i][j]; } trie1.add_word(word1); trie2.add_word(word2); } vector<int> ans; for(int i=0;i<m;i++) { string word1,word2; for(int j=0;j<t[i].size();j++) { if(j%2==0) word1+=t[i][j]; word2+=t[i][j]; } int a=trie1.pre_fun(word1);//奇数位匹配数量 int b=trie2.pre_fun(word2);//完整单词匹配数量 if(a>0 && b==0) //奇数位匹配了a个 偶数位没有一个匹配上 ans.push_back(a); else if(a==0 && b==0) //都没匹配上 ans.push_back(0); else if(t[i].size()==1) ans.push_back(a); else ans.push_back(a-b);//其它情况 选取那些满足要求的 } return ans; } };
