java - 在 Java 中将一个字符串重新排列为另一个字符串

Question

我试图找出给定字符串 A 的一部分是否可以重新排列为给定字符串 B( boolean 输出)。
由于算法必须至多为 O(n)，为了简化它，我使用了 stringA.retainAll(stringB)，所以现在我知道字符串 A 和字符串 B 由相同的字符集组成，现在整个任务闻起来像正则表达式。
而且 .. 阅读有关正则表达式的内容，我现在可能有两个问题(c)。
问题是，我是否可能面临通过使用正则表达式或更有效地使用 StreamAPI 来获得 O(infinity) 的风险，目的是查找字符串 A 的每个字符是否具有足够的重复项来覆盖字符串 B 的每个字符？更不用说正则表达式语法不容易阅读和构建。
截至目前，我不能使用排序(任何排序至少为 n*log(n))，也不能使用哈希集等(因为它消除了两个字符串中的重复项)。
谢谢。

Answer 1

您可以使用 HashMap<Character,Integer>计算第一个String的每个字符出现的次数.这将花费线性时间。

然后，对于每个 Character第二个String , 查找它是否在 HashMap 中并减少计数器(如果它仍然是正数)。这也将花费线性时间，如果您设法减少第二个 String 的所有字符的计数器, 你成功了。