pony挂经

各自介绍一下，就开始做题。

给定一个字符串 s1 =  “abcabcaaef“， 一个数组["aaa&qu

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

度，还没有实现完优化的方法，时间就走完了。他们家的面经重复的概率很小。。。。

跟二楼稍微不一样。
直接用map记录每个字符串出现的indexes。
然后走数组，数组里每个char都选上面能选的最小的index，如果选不到就不行。能选到最后就可以了，挺简单的

aabaa 发表于 2019-2-19 15:29
“abcabcaaef“ 并没有 “aaa”的子串啊，难道我理解错误？

有啊，不需要连续，找到一个子序列就行。

预处理是s1，记录下每个位置开始的下一个a-z字符的位置。
后面的就简单了，基本上是线性的时间复杂度。

数组做个trie 原字符串挨个查？

后缀树？

补充内容 (2019-2-11 20:33):
例如S: leconte，查找o: con是否在S中,则o(con)必然是S(leconte)的后缀之一conte的前缀.有了这个前提，采用trie搜索的方法就不难理解了。
https://blog.csdn.net/v_JULY_v/article/details/6897097

(不知道为什么 发帖被系统自动隐藏了

可以用后缀树

例如S: leconte，查找o: con是否在S中,则o(con)必然是S(leconte)的后缀之一conte的前缀.有了这个前提，采用trie搜索的方法就不难理解了。
https://blog.csdn.net/v_JULY_v/article/details/6897097

感觉他家面试的难度与（候选人背景， 应聘岗位）有关。。。

“abcabcaaef“ 并没有 “aaa”的子串啊，难道我理解错误？

Thanks for sharing

这是里扣漆久贰