您可以在O(N+M)
时间和O(1)
空间上进行直方图扫描,其中N
是第一个字符串中M
的字符数,而第二个字符串中的字符数。
它是这样的:
请注意,通过改变您在直方图条件上使用的检查,您可以选择具有 与 第二个字符串 相同的字符集 ,或者 每种类型的字符数最少 。(它只是之间的差异a[i]>0 && b[i]>0
和a[i]>=b[i]
。)
如果您跟踪想要满足的条件不满足的条件,则可以加快直方图的检查速度,并在尝试破坏条件时仅检查您递减的值。(在初始构建时,您要计算满足的项目数,并在每次添加将条件从false变为true的新字符时递增该计数。)