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

Question

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

如果不将第一个字符串中的每个字符与第二个字符串的并行字符进行比较，我无法弄清楚如何检查它。

Answer 1

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

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

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

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

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