[阿里巴巴二面]两个字符串A、B,从A中剔除存在于B中的字符。


两个字符串A、B,从A中剔除存在于B中的字符。比如A=“hello world”,B="er",那么剔除之后A变为"hllo wold"。空间复杂度要求是O(1),时间复杂度越优越好。
已邀请:

如果A、B中出现的字符串有一个限制的话,比如都是ASCII码,那么我们可以做一个bitmap,开一个大小为N(如ASCII码N为127)的布尔数组分别表示N个字符是否在B中出现,然后扫描B一次扫描A一次就可以了,这样也算空间复杂度为o(1).

实在不行就先对B做一遍快排,时间复杂度nlogn空间复杂度O(1),在对A中每个元素在B中做二分查找看是否有重复,这时最终的复杂度为(m+n)logn。

要回复问题请先登录注册