algorithm - 在 Python 中检查两个字符串是否是彼此的排列

Question

我正在检查两个字符串 a 和 b 是否是彼此的排列，我想知道在 Python 中执行此操作的理想方法是什么。来自 Python 之禅，“应该有一种——最好只有一种——显而易见的方法”，但我认为至少有两种方法:

sorted(a) == sorted(b)

和

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

但是当(例如)a 的第一个字符在 b 中不存在时，第一个比较慢，而当它们实际上是排列时，第二个比较慢。

有没有更好的方法(在更 Pythonic 的意义上，或者在平均更快的意义上)？或者我应该根据我预计最常见的情况从这两个中进行选择？

Answer 1

这是一种 O(n) 的方法，渐近优于您建议的两种方法。

import collections

def same_permutation(a, b):
    d = collections.defaultdict(int)
    for x in a:
        d[x] += 1
    for x in b:
        d[x] -= 1
    return not any(d.itervalues())

## same_permutation([1,2,3],[2,3,1])
#. True

## same_permutation([1,2,3],[2,3,1,1])
#. False