检查两个字符串的排列

Question

我确实有一个问题,我正在尝试使用最有效的方法来解决它.

"给定两个字符串,找出两个字符串是否相互排列."

我知道直截了当的方法(即排序两个字符串)等.

我想看看我的方法是否适用于所有情况,我不确定,所以我需要你的意见和你的意见.

def CheckPermutaionsBySumUp(firstString, secondString):
   if (len(firstString) != len(secondString)):
      return False

   firstStringCount = 0
   secondStringCount = 0

   for char in firstString:
      firstStringCount += ord(char)

   for char in secondString:
      secondStringCount += ord(char)

   if firstStringCount == secondStringCount:
      return True

   return False

所以我的方法是,我确实有一个有用的约束,并且如果两个字符串的长度不同,那么这两个字符串不是彼此的排列.

然后,知道每个字符都有唯一的数字表示,如果我使用ord函数总结每个字符串的每个字母的数量,我可以比较两个总和并找出这两个字符串是否是排列.在我看来,这个解决方案不仅仅是O(n),而且比使用数组和数据结构更节省空间.

我唯一担心的是,有两个字符串,长度相同,字符不同,有相同的总和吗？

Answer 1

如果需要O(n)解决方案,请使用每个字符串中的字符计数:

from collections import Counter
def is_anagram(a,b):
    if len(a) != len(b):
         return False
    return  Counter(a) == Counter(b)

如果你有一个字谜,每个字符串的数量和字母必须相同:

In [45]: is_anagram("foo","oof")
Out[45]: True

In [46]: is_anagram("foobar","raboof")
Out[46]: True

In [47]: is_anagram("foobar","foo")
Out[47]: False