如何检查两个字符串在Python中是否是彼此的排列组合?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (124)

我在检查两条线ab是彼此之间的排列组合,我想知道用Python实现这一点的理想方法是什么。从Python的禅宗来看,“应该有一种--最好只有一种--显而易见的方法,”但我认为至少有两种方法:

sorted(a) == sorted(b)

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

但是当(例如)a无处可寻b,当它们实际上是排列时,第二步要慢一些。

有什么更好的方法?

提问于
用户回答回答于

从启发式的角度来看,您最好根据字符串大小将它们分开。

伪码:

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

如果性能非常关键,并且字符串大小可以是大的或小的,那么我就会这样做。

用户回答回答于

这里有一种方法是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

扫码关注云+社区

领取腾讯云代金券