前几天的 骨骼店面

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

感谢！受教了

xiaocase 发表于 2018-8-10 11:16
感谢！受教了

不敢不敢，我也是先写了个O(n^3)的DP优化了一个小时想出来的。。。

恭喜楼主！

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

这样如果B里面的字符有重复会不会有问题啊？比如B是“ABCDA”，这样A的顺序好像就没办法处理了

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

对的 刚刚我把思路写代码的时候发现这个问题不行 xxw289的做法是对的 你可以去参考代码！！

补充内容 (2018-8-10 14:03):
谢谢指出~~~~~(๑•̀ㅂ•́)و✧

请问一下，你的oa是什么题目呢？？

很有用的信息！

ivanyang 发表于 2018-8-10 06:54
这个感觉可以dfs + memorization
记录下sub  string 是否可以由挖去字符串构成就行。

这样就要记录下所有的substring， 空间复杂度很高吧

gongpumiao0 发表于 2018-8-10 17:13
请问一下，你的oa是什么题目呢？？

是求最接近时间和开花问题的变种

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

ABCABCDD, ABCD