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

输入两个子串,记作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继续

实在不知道咋写了,感觉不太好实现,有没有老哥会这个题的,可否提供一下答案呢,谢谢!
#字节面试##字节跳动##笔试题目#
全部评论
我觉得可以用双指针ij。大概思路就是逐渐增大ij之间的窗口大小,当大小等于p时就匹配成功了。 每次迭代,j指针指向下一个字符,当下一个字符数量已经超出时,向右移动i至当前字符值的下一个位置。 时间复杂度O(n). 输入: t=CABABBABC p=ABBC 迭代(左右括号代表ij): - []CABABBABC - [C]ABABBABC - [CA]BABBABC - [CAB]ABBABC - CA[BA]BBABC // 此处A的数量已经超出,所以i移动到了第一个A后面 - CA[BAB]BABC - CAB[ABB]ABC// 此处B的数量已经超出,所以i移动到了第一个B后面 - CABA[BBA]BC - CABAB[BAB]C - CABAB[BABC] // ij之间距离==4,return
点赞 回复
分享
发布于 2022-04-11 14:30
排序然后用kmp?
点赞 回复
分享
发布于 2023-02-03 03:19 四川
滴滴
校招火热招聘中
官网直投

相关推荐

点赞 4 评论
分享
牛客网
牛客企业服务