题解 | #单双难全#

单双难全

http://www.nowcoder.com/practice/9e1551271e074f3eb7e9232f6e7846a3

算法思想一:暴力法

解题思路:

遍历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的遍历时间

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

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-28 10:16
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
1 收藏 评论
分享

全站热榜

正在热议