检查两个字符串的排列

Question

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

"Given two strings, find out if the two strings are permutation of each other."

我知道最简单的方法（即对两个字符串进行排序）等等

我想看看我的方法是否适用于所有情况，但我不确定，所以我需要您的意见和意见。

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)，而且确实 space-比使用数组和数据结构更高效。

我唯一担心的是，两个长度相同但字符不同的字符串是否有可能具有相同的总和？

Answer 1

您的推理，以及您的方法在一般情况下并不成立。一个快速的反例：

firstString = 'ad'

secondString = 'bc'

两个字符串的长度都是2，字符总和为197。

Answer 2

相同长度的两个完全不同的字符串可能具有相同的总和。

例如：

 '03' # Sum: 99
 '12' # Sum: 99

这样想：

如果您增加一个字符的值（通过写“1”而不是“0”），您只需将另一个字符的值减少相同的量即可使其平衡。添加字符值不足以检查排列。

Answer 3

如果您想要 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

Answer 4

str1 = raw_input('Enter First String: ')
str2 = raw_input('Enter Second String: ')

def check_permutation(str1, str2):
    if(len(str1) != len(str2)):
        return 'Not Permutation strings'
    #initialize the track_duplicates to 0 to track if the exsisting character at the index of str2 is already matched
    track_duplicates = [0] * len(str2) 
    is_permutations = True
    for c1 in str1:
        c1_in_str2 = False
        i = 0
        for c2 in str2:
            if(c1 == c2 and track_duplicates[i] is 0):
                c1_in_str2 = True
                track_duplicates[i] = 1
                break
            i += 1
        if(not c1_in_str2):
            is_permutations = False
            break
    if(is_permutations):
        return 'Permutation Strings'
    else:
        return 'Not Permutaions Strings'


print(check_permutation(str1, str2))

Answer 5

def permutation(s1, s2):
    if len(s1) != len(s2): 
        return False
    return ' '.join(sorted(s1)) == ' '.join(sorted(s2))

检查两个字符串的排列

Check Permutation of two strings

python

permutation

anagram