前几天的 骨骼店面

oo小天使oo 发表于 2018-8-10 10:31
可不可以用一个hashmap存B中character和对应的顺序值
例如 B是“ABCD“” 那么hashmap中 A-1 B-2 C-3 D-4
...

那如果B= “ABCA” 就不太对了

xxw289 发表于 2018-8-10 11:11
这题我想用greedy从A中匹配尽量多的B中的元素（用反证法可以证出这样肯定最少），然后双指针扫A和B,B扫完了 ...

很厉害的解法，想请问下，双指针这样的是怎么计算出来的时间复杂度呢？

TomD 发表于 2018-8-11 03:39
很厉害的解法，想请问下，双指针这样的是怎么计算出来的时间复杂度呢？

我觉得我说错了，时间复杂度应该是O(m * n).
看这个例子：A = "CCCCCCCC", B = "DDDDDC", 每匹配一个A中的C都要扫一遍B.

我觉得找出A和B的count， 然后相除， 如果A的某个字符大于0的同时B的这个字符小于0， 那么就是不存在， 然后把A的frequency 除以B的frequency 加上1 假设A ="AAAAA" B = "AA" 5/2 默认是2 因为ceiling的缘故， 但是实际上是需要至少3个B来组成A，所以就找哪个倍数最大的那个就是了
"

xxw289 发表于 2018-8-11 06:22
我觉得我说错了，时间复杂度应该是O(m * n).
看这个例子：A = "CCCCCCCC", B = "DDDDDC", 每匹配一个A中 ...

嗯，那就和我想的一样了，谢谢！

xxw289 发表于 2018-8-10 11:11
这题我想用greedy从A中匹配尽量多的B中的元素（用反证法可以证出这样肯定最少），然后双指针扫A和B,B扫完了 ...

感觉有个bug… 如果串1是aaabc，串2是aabcaaa，结果应该是2，这个算法似乎会return -1？

chrislee 发表于 2018-8-16 13:23
感觉有个bug… 如果串1是aaabc，串2是aabcaaa，结果应该是2，这个算法似乎会return -1？

不会啊，先匹配了aaa后匹配了bc，他是每次都把j归0了。不过感觉不好之处在于，时间复杂度最坏情况是O(mn)而不是O(m+n)，比如aaaaaaaa和abcdefghi

sean1993519 发表于 2018-8-17 01:51
不会啊，先匹配了aaa后匹配了bc，他是每次都把j归0了。不过感觉不好之处在于，时间复杂度最坏情况是O(mn) ...

哦哦这个例子没举例好  abcabcdd 和 abcadd 这个返回2，正确答案应该是3。 不能光reset j，还得reset i.

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

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