首页 > 试题广场 >

单双难全

[编程题]单双难全
  • 热度指数：538 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有n个只包含小写字母的串s_1,s_2,..s_n，每次给你一个只包含小写字母的串t。如果串S存在前缀S'，它的奇数位的字符与t的奇数位字符完全相同，称S为t的单匹配串，如果串S的偶数位字符与t的偶数位的字符全都相同，称S为t的双匹配串。
现在给你m个字符串，对于每个字符串t_i，求s_1,s_2,...s_n中有多少个串是t的单匹配串但不是t的双匹配串。


示例1

输入

3,["abc", "bbc", "cbd"],3,["abc","cad","bac"]

输出

[0,1,1]

说明

对于字符串"abc"。没有满足条件的单匹配串
字符串“cad"有满足条件的串: "cbd" ,第一个位置都是c，第三个位置都是d，是单匹配串，但是第二个位置不同，不是双匹配串
字符串"bac"有满足条件的串: "bbc" ,第一个位置都是b，第三个位置都是c，是单匹配串，但是第二个位置不同，不是双匹配串

备注:
算法知识视频讲解
开通博客
头像 Maokt
发表于 2021-08-03 20:51:14
算法思想一：暴力法 解题思路： 遍历t数组，枚举每一个s进行比较。 依次遍历 t 取出元素 it， 再取出 s 中元素 is : 通过 去除 s 中非 it 单匹配串的字符串， 再比较 ，去除满足双匹配的字符串。 在统计剩余字符串中满足单匹配串的个数。 图解： 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 漫漫云天自翱翔
发表于 2021-08-18 10:45:16
NC524 单双难全题解一：字典树题解思路： 构建两个字典树，一个用字符串奇数位构建，一个用字符串的全部字符创建一个字典树图示字典树：复杂度分析:时间复杂度： :建树的时间复杂度由字符串长度决定，查找前缀树取决前缀长度。 建树需要遍历s字符串数组中的每个字符串，查找需要遍历t字符串数组中的每个字符 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-03 19:46:03
思路： 题目的主要信息： 字符串t与字符串s的前缀（从头开始，取前t.length个），若是二者所有的奇数位字符串都相等则称之为单匹配，若是二者所有偶数位字符串都相等，则称之为双匹配 奇数偶数下标从1开始，注意与字符串下标之间的关系 需要求m个t字符串，各自在n个s字符串中有多少属于单匹配但不属于 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 xqxls
发表于 2021-08-06 18:08:17
题意整理 给定个字符串组成的字符串数组，以及个字符串组成的字符串数组。 对于中的每一个字符串，如果s数组中存在某个字符串的前缀与单匹配，但不满足双匹配，求这样的字符串有多少个。 方法一（暴力匹配） 1.解题思路 首先固定t数组的某一个字符串，然后遍历s数组，将s数组中的每一个字符串与t数组固定 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 积极的防守者
发表于 2020-02-10 21:30:26
普通解法 直接对于每个暴力枚举每个是否满足条件因为枚举每个的的时候，最多进行次匹配，所以总的时间复杂度为用了几个中间变量存值，空间复杂度 vector<int> solve2(int n, vector<string> s, int m, vector<string&g 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 认认真真coding
发表于 2021-08-05 17:14:26
题目描述有n个只包含小写字母的串s1,s2,..sn，每次给你一个只包含小写字母的串t。如果串S存在前缀S'，它的奇数位的字符与t的奇数位字符完全相同，称S为t的单匹配串，如果串S的偶数位字符与t的偶数位的字符全都相同，称S为t的双匹配串。现在给你m个字符串，对于每个字符串ti，求s1,s2,... 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

字符串 字典树
难度：
2条回答 4340浏览

热门推荐

通过挑战的用户

查看代码

相关试题

单双难全

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号