string - 相似字符串比较算法

Question

在最近的一次采访中得到了这个问题。基本字符串比较有一点扭曲。我有一个输入字符串 STR1 = 'ABC'。当要比较的字符串时，我应该返回“相同/相似”，STR2 具有这些值中的任何一个 - 'ACB' 'BAC' 'ABC' 'BCA' 'CAB' 'CBA' (即相同的字符，相同的长度和相同的编号发生次数)。当时唯一的答案是继续“合并排序”或“快速排序”，因为它的复杂性是对数的。有没有其他更好的算法可以达到上面的结果？

Answer 1

对两者进行排序，并比较结果是否相等，对于长度合理的字符串来说是一个不错的方法。

另一种方法是使用映射/字典/对象(取决于语言)从字符到出现次数。然后，您遍历第一个字符串，递增计数，并遍历第二个字符串，递减计数。您可以在得到负数后立即返回 false。

如果您的可能字符集小到足以被视为常量，则可以使用数组作为“映射”，从而导致 O(n) 最坏情况的复杂度。