检查字符串中所有字符是否唯一的方法的复杂性

Question

我正在尝试在 kotlin 中编写一个函数来检查字符串中的所有字符是否都是唯一的。

fun isUnique(s: String): Boolean {
     return s.filter {
          char -> s.count(char) == 1
     } == s
}

我想知道这个方法的运行时复杂度是多少。是 O(n) 还是 O(n pow2)（因为我们在 filter 函数和 count 函数中两次触摸每个字符）？ space 复杂度也是 O(1)?

或者，我写了这个方法

fun isUnique2(s: String): Boolean {
    return s.groupBy {
        char -> s.count(char)
    }.filterKeys{key > 1}.isEmpty()
}

这个方法的space和时间复杂度是多少？

感谢任何帮助

谢谢

Answer 1

第一个实现是 O(n^2)，不仅仅是因为您触摸每个字符两次（由于 ==，它实际上是 4 次，但如果您比较大小的话可能只是两次），但是因为对于您在过滤器中考虑的 each 字符，您通过 count().

迭代字符串的整个 N 个字符

将字符串迭代两次和对字符串的每个字符迭代一次字符串是不一样的。这就是O(2n) (= O(n)) 和O(n^2) 的区别。

第一个实现还分配了一个带有过滤元素的额外集合，在最坏的情况下包含所有字符，因此 O(n) space.

第二个实现做更多的工作，你仍然从 O(n^2) 步骤开始，因为你 count 通过整个字符串来构建每个组。但是随后您会增加更多 space 复杂性，因为您分配了更多的中间集合。

您可以得到一个复杂度为 O(n) 的解决方案，复杂度为 O(n) space 只需将您的字符串转换为 Set 并比较大小：

fun isUnique(s: String): Boolean { return s.toSet().size == s.length }

在内部，toSet() 使用 LinkedHashSet，插入的摊销成本为 O(1)。这意味着字符串仅迭代一次，并且每个字符都以 O(1) 的时间插入到集合中，这确保在插入时没有重复项。比较大小通常也是 O(1)，因为大多数集合都有一种成本不变的方式来访问它们的大小。

Answer 2

两种实现的时间复杂度分别为 O(n^2) 和 O(n) space。

使用以下解决方案，在最坏的情况下，您可以拥有 O(n) 的时间复杂度（保持 O(n) space）：

fun isUnique(s: String): Boolean {
    val hashset = hashSetOf<Char>()
    return s.all { hashset.add(it)  }
}

但通常这个算法可能会在到达字符串末尾之前结束（返回false）（如果我们遇到一些重复的字符，不需要检查剩余的字符），所以在最好的情况下它可能会结束在第 2 次迭代中。

这背后的魔法由两部分组成：

add 方法 Set returns false 如果此集合已包含指定元素
all 方法 returns false 第一个谓词，计算结果为 false

检查字符串中所有字符是否唯一的方法的复杂性

Complexity of a method checking whether all characters in the string are unique

algorithm

big-o

kotlin