首页 > 求问一个关于字符串的字节面试算法题,优化不出来了
头像
Alwaysion
编辑于 2021-08-24 16:35
+ 关注

求问一个关于字符串的字节面试算法题,优化不出来了

输入两个子串,记作t,p,求t中是否存在p的子串,子串的定义为所含有的元素的数量完全相同,顺序可以不同。若存在,则返回-1,若存在,则返回index。
例如:
输入:
t=CABABBABC
p=ABBC
输出:
5
解析:
CABAB【BABC】中括号的位置为子串

这个题一开始用滑动窗口+字典统计个数AC了,但是面试官说这样的滑动窗口是一个一个往后遍历的,让优化一下(感觉是类似于KMP那种,一次性跳好几个index)
比如当遍历到index=0的时候,个数统计:A=2 B=1 C=1,A的个数超过了p中的A的个数,此时直接将index跳到第二个A,即从index=3继续

实在不知道咋写了,感觉不太好实现,有没有老哥会这个题的,可否提供一下答案呢,谢谢!

全部评论

(2) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐