骨骼 熱呼呼的掛經

店面:strA: ‘‘SDSD’’
strB: ‘‘ADS’’
請問幾次能複製過去
從strB上: S -> DS -> D
所以複製三次

請問有人知道這是哪一題嗎?

1.問時間複雜度
2.Follow up 如何優化

順便破謠言
我問了是否人的一生只能跟骨骼面三次
小哥答: 沒這回事

补充内容 (2018-9-29 07:07):
最近求職季節
存糧不夠
在勞請大家給點度過求職季
謝謝大家

这个题很高频啦 在地里见到不下四次吧。。 就是从b里挖去字母 构成 a, 最多需要几个b two pointer 和 dfs都可以做

为啥我没看懂你题目的意思…

strA = ‘‘SDSD’’
strB = ‘‘ADS’’
複製:
第一次 第二次 第三次
‘’##S’’ ‘’#DS’’ ‘’#D#’’
S SDS SDSD

不知道這樣有沒有回答到你的問題

这题我的思路是判断是不是可能,不可能的话return,可能的话找出A和B的longest substring,把A分为三个部分,longest substring 左边的部分,右边的部分及其本身,然后递归找出左边部分需要的次数,右边需要的次数,return左边加右边加1。不知道这个思路对不对。。。

哦,不是找longest substring,是找一个最长的common string,让其为A的substring,为B的subsequence,这部分可以用dp来做

后缀树加贪心?也许是我想复杂了

dp+kmp可以出来吧

求不要用kmp 不是人人都搞acm

这个就是问用几个strB可以组成strA吧 可以从前后删除 不可以从中间删除

prefix tree