前几天的 骨骼店面

chrislee 发表于 2018-8-16 16:58
哦哦这个例子没举例好  abcabcdd 和 abcadd 这个返回2，正确答案应该是3。 不能光reset j，还得reset i.

咦我怎么感觉正确答案就是2，第一次abca，第二次bcdd（根据楼主题意，每次选的可以不是str2的substring而是subsequence）

sean1993519 发表于 2018-8-17 07:36
咦我怎么感觉正确答案就是2，第一次abca，第二次bcdd（根据楼主题意，每次选的可以不是str2的substring而 ...

如果这么理解的话 aaabaa和 aabaaab正确答案是1，这个code的结果是2

duohedianshuiha 发表于 2018-8-10 13:43
这样如果B里面的字符有重复会不会有问题啊？比如B是“ABCDA”，这样A的顺序好像就没办法处理了

有重复也没关系，那就在每个char后面用一个类似于stack的玩意记录index，比如ABCA那就是A[0,3], B[1], C[2]，每次在需要一个新的B的时候把这个dict of stack复制一次，假设出现一次A就把0 pop掉，这样哪怕再出现一个A，也不会需要一个新的B，因为3大于0

补充内容 (2018-8-17 09:25):
哦不对这么做不行，有些问题没法解决

补充内容 (2018-8-17 09:26):
得随时pop掉那些已经小于当前index的值，这么看虽然O没变但是实际效率低很多

chrislee 发表于 2018-8-16 20:37
如果这么理解的话 aaabaa和 aabaaab正确答案是1，这个code的结果是2

我如果没有理解错，他这个题是，str2可以挖，但是str1必须是连续的。。。。不过我也是看他的例子感觉的

sean1993519 发表于 2018-8-17 12:22
我如果没有理解错，他这个题是，str2可以挖，但是str1必须是连续的。。。。不过我也是看他的例子感觉的

是的哇 str1是 aaabaa, str2是aabaaab
str1: aaab | aa, 利用一个str2 aa | b | aaab 就可以

chrislee 发表于 2018-8-17 01:01
是的哇 str1是 aaabaa, str2是aabaaab
str1: aaab | aa, 利用一个str2 aa | b | aaab 就可以

他不能顺序颠倒啊

sean1993519 发表于 2018-8-17 13:17
他不能顺序颠倒啊

限制条件这么多这code已经有点危险. 走个code流程会发现其实里面的invariant已经违背了. 即使按照顺序也不能改变也有反例:
str1: deadcd
str2: addedc 用2个就够了

str1 = de | ad | c | d
str2 : 第一个 ad | de | d | c 选de 和 d
         第一个 ad | de | d | c 选ad 和 c

这个code跑出来是3个

chrislee 发表于 2018-8-17 02:04
限制条件这么多这code已经有点危险. 走个code流程会发现其实里面的invariant已经违背了. 即使按照顺序也 ...

我理解的楼主的例子意思是从str2挖characters一点一点构建str1，所以str1是substring，str2是subsequence（正如我前面说的）。。。如果按照这个理解你的例子本来就应该是3，因为你选de 和 d这两个隔过去了别的。。。不过我觉得这个没什么探讨的必要了，到时候具体要求具体做。。

很有用的信息！

可以使用任意次B,每次可以挖去任意次字符。难道不是建两个hashmap, 形式是：letter:count。能不能构成就看B是不是包括A的所有letter，最少次就是对应letter count相除最大值的ceil。复杂度都是O(n)