一尘不染

检查两个字符串是否在Python中彼此置换

algorithm

我正在检查两个字符串ab是否彼此置换,并且想知道在Python中执行此操作的理想方法是什么。在Python的Zen中,“应该有一种-最好只有一种-
明显的方式来做到这一点,”但我看到至少有两种方式:

sorted(a) == sorted(b)

all(a.count(char) == b.count(char) for char in a)

但是第一个字符较慢时(例如)的第一个字符在a中不存在b,而第二个字符实际上是置换时则较慢。

有没有更好的方法(从更Pythonic的角度来看,或者从平均而言更快)?还是应该根据我希望最常见的情况从这两个中进行选择?


阅读 311

收藏
2020-07-28

共1个答案

一尘不染

启发式地,您最好根据字符串大小将它们分开。

伪代码:

returnvalue = false
if len(a) == len(b)
   if len(a) < threshold
      returnvalue = (sorted(a) == sorted(b))
   else
       returnvalue = naminsmethod(a, b)
return returnvalue

如果性能至关重要,并且字符串大小可以大或小,那么这就是我要做的。

根据输入的大小或类型分割这样的事情是很常见的。算法具有不同的优势或劣势,在另一种更好的情况下使用一种算法是愚蠢的。在这种情况下,Namin的方法为O(n),但常数因子比O(n
log n)排序的方法大。

2020-07-28