前几天的 骨骼店面

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扫完了 ...

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

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

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

我觉得找出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？

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

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

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

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

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

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