题解 | #单双难全#

题意整理

给定 $n$ 个字符串组成的字符串数组 $s$ ，以及 $m$ 个字符串组成的字符串数组 $t$ 。
对于 $t$ 中的每一个字符串 $t_i$ ，如果s数组中存在某个字符串的前缀与 $t_i$ 单匹配，但不满足双匹配，求这样的字符串有多少个。

方法一（暴力匹配）

1.解题思路

首先固定t数组的某一个字符串，然后遍历s数组，将s数组中的每一个字符串与t数组固定的那一个字符串带入match函数，如果匹配，则对应结果集加一。
match函数主要检查s串是否是t串的单匹配串而不是t串的双匹配串，由于只检查是否有满足条件的s的前缀，所以只需遍历t串长度，如果奇数项不匹配，说明不是单匹配，直接排除，如果偶数项匹配，说明是双匹配，也直接排除，到最后仍然满足条件的，返回true。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 单双难全
     * @param n int整型 字符串s的个数
     * @param s string字符串一维数组 n个字符串s
     * @param m int整型 字符串t的个数
     * @param t string字符串一维数组 m个字符串t
     * @return int整型一维数组
     */
    public int[] solve (int n, String[] s, int m, String[] t) {
        //初始化结果集
        int[] res=new int[m];

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                //满足单匹配但不满足双匹配，则计数加一
                if(match(t[i],s[j])){
                    res[i]++;
                }
            }
        }
        return res;
    }

    private boolean match(String t,String s){
        int n=t.length();
        for(int i=0;i<n;i++){
            //如果奇数位不匹配，直接返回false
            if(i%2==0&&t.charAt(i)!=s.charAt(i)){
                return false;
            }
            //如果某个偶数位匹配，直接返回false
            if(i%2==1&&t.charAt(i)==s.charAt(i)){
                return false;
            }
        }
        //整个t串满足单匹配不满足双匹配
        return true;

    }
}

3.复杂度分析

时间复杂度：假设s数组长度为n，t数组长度为m，显然两层循环遍历了 $m*n$ 次，而每次match函数执行的次数取决于t数组中每个字符串的长度，所以总共的执行次数是n* $图片说明$ （ $|t_i|$ 是t数组中第i个字符串的长度），最终的时间复杂度是O(n* $图片说明$ )。
空间复杂度：需要额外常数级别的内存空间，所以空间复杂度是 $O(1)$ 。

方法二（字典树找前缀）

1.解题思路

首先初始化两个字典树结构，一个普通字典树，一个单匹配字典树。
每个字典树中提供两个方法，一个insert，一个findPreNum，insert用于向字典树中插入字符节点，findPreNum用于查找对应前缀在字典树的数目。
字典树构造好之后，就分别向字典树中插入s数组的字符串，然后在t数组中进行查找，对于t数组中的某一个字符串，单匹配字典树中出现次数减去全匹配字典树中出现次数即为符合条件串的数目。如果当前字符串长度为1，则满足全匹配也是单匹配而不是双匹配，所以只考虑单匹配。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 单双难全
     * @param n int整型 字符串s的个数
     * @param s string字符串一维数组 n个字符串s
     * @param m int整型 字符串t的个数
     * @param t string字符串一维数组 m个字符串t
     * @return int整型一维数组
     */
    public int[] solve (int n, String[] s, int m, String[] t) {
        //初始化结果集
        int[] res=new int[m];

        //初始化字典树
        Trie trie=new Trie();
        OddTrie oddtrie=new OddTrie();
        for(int i=0;i<n;i++){
            //往字典树插入字符串
            trie.insert(s[i]);
            oddtrie.insert(s[i]);
        }

        for(int i=0;i<m;i++){
            //单匹配字典树中出现次数减去全匹配字典树中出现次数即为符合条件串的数目
            res[i]=oddtrie.findPreNum(t[i])-trie.findPreNum(t[i]);
            //如果长度为1，则满足全匹配也是单匹配而不是双匹配，所以只考虑单匹配
            if(t[i].length()==1){
                res[i]=oddtrie.findPreNum(t[i]);
            }
        }
        return res;
    }


}
//全匹配字典树
class Trie{
    //子节点数组
    Trie[] child;
    //记录前缀出现数目
    int cnt;
    Trie(){
        this.child=new Trie[26];
        this.cnt=0;
    }

    //往字典树中插入字符串
    void insert(String s){
        Trie node=this;
        char[] arr=s.toCharArray();
        for(char c:arr){
            if(node.child[c-'a']==null){
                node.child[c-'a']=new Trie();
            }
            node=node.child[c-'a'];
            node.cnt++;
        }
    }

    //查找树中以t为前缀的字符串数目
    int findPreNum(String t){
        Trie node=this;
        char[] arr=t.toCharArray();
        for(char c:arr){
            if(node.child[c-'a']==null){
                return 0;
            }
            node=node.child[c-'a'];
        }
        return node.cnt;
    }

}
//单匹配字典树
class OddTrie{
    //子节点数组
    OddTrie[] child;
    //记录前缀出现数目
    int cnt;
    OddTrie(){
        this.child=new OddTrie[26];
        this.cnt=0;
    }

    //往字典树中插入字符串
    void insert(String s){
        OddTrie node=this;
        char[] arr=s.toCharArray();
        for(int i=0;i<arr.length;i+=2){
            char c=arr[i];
            if(node.child[c-'a']==null){
                node.child[c-'a']=new OddTrie();
            }
            node=node.child[c-'a'];
            node.cnt++;
        }
    }

    //查找树中以t为前缀的字符串数目
    int findPreNum(String t){
        OddTrie node=this;
        char[] arr=t.toCharArray();
        for(int i=0;i<arr.length;i+=2){
            char c=arr[i];
            if(node.child[c-'a']==null){
                return 0;
            }
            node=node.child[c-'a'];
        }
        return node.cnt;
    }

}

3.复杂度分析

时间复杂度：插入的复杂度取决于插入字符串的长度，查找前缀数的复杂度取决于前缀的长度，所以总共插入的次数为s数组中所有字符串长度之和，总共查找的次数为t数组中所有字符串长度之和，假设 $|t_i|$ 是t数组中第i个字符串的长度， $|s_i|$ 是s数组中第i个字符串的长度，最终的时间复杂度是O( $图片说明$ )。
空间复杂度：假设 $Σ$ 表示组成字符串的字符种数（本题为26），每个节点需要 $Σ$ 大小的子节点数组，总共插入了s数组中所有字符组成的节点，所以空间复杂度为O(Σ* $图片说明$ )。