leetcode 467. 环绕字符串中唯一的子字符串
2024-08-22 19:01:39
题目描述:
把字符串 s
看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串,所以 s
看起来是这样的:"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
现在我们有了另一个字符串 p
。你需要的是找出 s
中有多少个唯一的 p
的非空子串,尤其是当你的输入是字符串 p
,你需要输出字符串 s
中 p
的不同的非空子串的数目。
注意: p
仅由小写的英文字母组成,p 的大小可能超过 10000。
示例 1:
输入: "a"
输出: 1
解释: 字符串 S 中只有一个"a"子字符。
示例 2:
输入: "cac"
输出: 2
解释: 字符串 S 中的字符串“cac”只有两个子串“a”、“c”。.
示例 3:
输入: "zab"
输出: 6
解释: 在字符串 S 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。
思路:如例3,当字符串为'z'时,子串只有'z',个数为1;当字符串为'za'时,字串有'z','a','za',个数为3,和字符串'z'相比,新增子串个数为2;
字符串'zab',新增子串有'b','ab','zab'3个。
也就是说按序的字符串每增加一个,新增的字串个数加1。
建一个数组,存储每次新增的子串个数,最后统计数组中数字的和。
题目链接:https://leetcode-cn.com/problems/unique-substrings-in-wraparound-string/
class Solution {
public:
int findSubstringInWraproundString(string p) {
int maps[];
int m[];
int len,num = ;
memset(maps,,sizeof(maps));
for(int i = ;i<p.size();i++)
{
if(i == )
{
len = ;
maps[p[i]-'a'] = ;
}
else
{
if(p[i-] == p[i]- || (p[i] == 'a' && p[i-] == 'z') ) //如果连续,则新增子串数加1
{
len++;
}
else
{
len = ;
}
if(len > maps[p[i]-'a']) //存储子串个数
{
maps[p[i]-'a'] = len;
}
}
} for(int i = ;i<;i++)
{
num = num + maps[i];
}
return num;
}
};
最新文章
- HTML5- Canvas入门(一)
- 关于prototype和__proto__ 以及 constructor的文字总结
- Unity3d - RPG项目学习笔记(一)
- Java之MS SQL数据库连接
- 拥抱模块化的JavaScript
- The xor-longest Path
- 【行为型】Chain of responsibility模式
- Redis VS Memcached 转载
- r语言之条件、循环语句
- Tuple
- 应用Git Flow—Git团队协作最佳实践
- VMWare的网络
- 第五节:WebApi的三大过滤器
- Vue学习4:class与style绑定
- 转载:关于JESD204B转换器与FPGA匹配的设计关键点
- [zz]如何学习Polygon Mesh Processing这本书?
- linux下如何删除行首的数字?
- WebSocket-Over-HTTP Protocol
- shell脚本遍历子目录
- macbook基本配置
热门文章
- js 移动端之监听软键盘弹出收起
- UCOSIII软件定时器
- [TensorFlow]Windows下安装并运行Hello World
- UML类图的几种关系总结
- MySQL Backup--Xtrabackup备份常见错误
- 解决linux下创建用户时出现 Creating mailbox file: 文件已存在
- keepalived,tomcat,memcache
- 使用docker 安装 LNMP
- P1600 天天爱跑步[桶+LCA+树上差分]
- Caused by: java.lang.IllegalStateException: Ambiguous mapping found