首页 > 试题广场 >

原根

[编程题]原根
  • 热度指数：571 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出n个只包含小写字母'a'~'z'的字符串，我们称一个字符串s_i为原根，当且仅当给出的其他任何字符串都不是它的前缀。

现在牛牛想知道给出的字符串中有多少个原根。
（相同字符串互为前缀）
示例1

输入

3,["a","ab","ba"]

输出

2

说明

"a"是原根
因为"a"是"ab"的前缀，所以"ab"不是原根
"ba"是原根

备注:

第一个参数n代表字符串个数
第二个参数vector s包含n个元素代表给出的字符串。
算法知识视频讲解
开通博客
头像 SandMonth
发表于 2021-09-09 16:59:33
原根 题目:给出n个只包含小写字母'a'~'z'的字符串，我们称一个字符串为原根，当且仅当给出的其他任何字符串都不是它的前缀。 案例输入：3,["a","ab","ba"]返回值：2说明："a"是原根因为" 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 xqxls
发表于 2021-08-18 11:31:21
题意整理 给定一个大小为n的字符串数组。 找出字符串数组中原根的个数。 给定一个字符串，其他任何字符串都不是它的前缀，则称为原根。 方法一（暴力法） 1.解题思路 直接遍历整个字符串数组，然后将当前字符串，与所有其他字符串进行比较，只要其他字符串中有一个是它的前缀，就不是原根，原根标记置为fal 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 CroMarmot
发表于 2021-10-01 04:40:20
题意 一个大小为nnn的字符串数组，默认所有贡献为1，如果一个字符串sis_isi​是sjs_jsj​的前缀，那么sjs_jsj​贡献为0 求所有字符串的贡献和 范围: n≤105n\leq 10^5n≤105 字符串所有字符总数≤106\leq 10^6≤106 解法 暴力模拟 我们把题意翻译成代 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 AimerAimer
发表于 2021-10-01 11:42:09
题意： 题目意思简化： 给出n个只包含小写字母'a'~'z'的字符串，如果存在一个其他串是某个串的前缀，则舍弃掉,问剩余串的数量？ 方法一： 直接模拟 思路：二重循环模拟，vis[i]初始值都为0，表示都未被舍弃。 如果s[i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-11 21:03:10
思路： 题目的主要信息： n个字符串，只有小写字母a-z 如果对于一个字符串，其他n-1个字符串都不是它的前缀，则它是原根 求这n个字符串中原根的数量 方法一：暴力法具体做法：我们可以暴力遍历每一个字符串，然后再分别与其他n-1个字符串进行比较，检查是否是它的前缀。检查前缀的时候，我们可以也是暴 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Ivy2019
发表于 2022-09-11 19:49:54
善用字符串比较函数 int compare (size_type pos, size_type n, const basic_string& s,size_type pos2, size_type n2) const; 从索引0开始比较，比较的长度为两个之中较短的字符串，即可以确 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Peterliang
发表于 2021-10-11 23:31:30
NC559 题解 | #原根# 题意分析 给我们n个字符串，对于某一个字符串，如果除了这个字符串本身之外的字符串都不是它的前缀，那么我们就称这个字符串为原根。问这n个字符串里面有多少个原根。 思路分析 解法一 暴力求解 首先，我们来进行暴力求解。我们先枚举每个需要进行判断的字符串a，然后枚举 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

字符串 字典树
难度：
6条回答 5967浏览

热门推荐

通过挑战的用户

查看代码

相关试题

原根

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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