骨骼 熱呼呼的掛經

店面:strA: 'SDSD'
strB: 'ADS'
請問幾次能複製過去
從strB上: S -&g

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

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

g>
最近求職季節
存糧不夠
在勞請大家給點大米度過求職季
謝謝大家

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

先预处理B,把所有子串存到hashmap里，O(N^2)
然后动态规划， f[i] 代表前i个字母最少需要几次，f[i] = min(f[j])+1,  B[j~i] 在hashmap 里， O(N^2)
总O(N^2)，不知道有没有更优解法

这个题挺tricky的。对于A的每个char，找在B里出现最早的，2pointer解决。i在A移动，j在B移动，取mod，找到了i++直到结束。当然要判断一下是不是能够造成（比如扫完了B一个长度的字符串还找不到A的char），最后返回j - 1 / B.length。贪心法的思想，不知道是不是最优的？

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

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可以出来吧

wxchit 发表于 2018-9-29 04:54
dp+kmp可以出来吧

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

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

prefix tree