python - 检查两个排序的字符串是否在 O(log n) 时间内相等

Question

我需要编写一个 Python 函数，它接受两个仅包含小写字母的排序字符串(每个字符串中的字符按字母顺序递增)，并检查这两个字符串是否相等。该函数的时间复杂度需要为O(log n)，其中n是每个字符串的长度。

如果不将第一个字符串中的每个字符与第二个字符串的平行字符进行比较，我不知道如何检查它。

Answer 1

事实上，在最坏的情况下，这在 O(log n) 时间内是可能的，因为字符串是由固定大小的字母组成的。

您可以对每个字符串进行 26 次二进制搜索，以找到每个字母在最左侧出现的位置。如果字符串相等，则所有 26 次二进制搜索将给出相同的结果；该字母在两个字符串中都不存在，或者它最左边的出现在两个字符串中相同。

相反，如果所有的二分搜索都给出相同的结果，那么字符串必须相等，因为 (1) 字母表是固定的，(2) 最左边出现的索引决定了每个字母出现的频率字符串，以及 (3) 字符串已排序，因此字母频率唯一确定字符串。

我在这里假设字符串具有相同的长度。如果不是，则首先检查并在长度不同时返回 False。获取字符串的长度需要 O(1) 的时间。

---

正如@wim 在评论中指出的那样，这个解决方案不能推广到数字列表；它特别适用于字符串。当您遇到涉及字符串的算法问题时，字母表的大小通常是一个常数，并且通常可以利用这一事实来实现比其他方式更好的时间复杂度。