Python 查找由变位词组成的最大子集的大小

本文教你如何编写一段Python程序来查找由变位词组成的最大子集的大小。

重新排列后的字符串或数字的每个字符也必须是另一个字符串或数字的组成部分，才能满足变位词的条件。换句话说，如果第二个字符串只是第一个字符串重新排列，那么这两个字符串就是变位词。例如，单词”The program”和”rogPrma”是变位词，单词”Code”和”doCe”也是变位词。

输入-输出情景

让我们看一个输入和输出情景，来查找由变位词组成的最大子集的大小。

Input: Facebook bookecFa Twitter ceaFkoob School 
Outpu: 3

在给定的输入中，只有3个字符串，即“Facebook”、“bookecFa”和“ceaFkoob”，它们都有8个字母的最大变位单词。因此，输出为3。

算法

以下是一种查找最大变位单词子集大小的算法：

• 获取用户输入的字符串并将它们放入单独的变量中。

• 使用sort()方法将两个字符串都排序成列表。

• 检查两个列表之间的变位形成。

• 打印结果。

• 退出。

示例

在上面声明了一个接受两个字符串作为输入的anagramCheck()方法。为了对这些字符串进行排序，创建了一个包含它们的列表。然后定义了一个位置变量并给它赋值为零。

在while循环的每次迭代中，比较字符串的长度和位置值。将两个列表中的每个项相互比较，并增加一个位置值。当位置值超过字符串的长度时，循环终止并返回true；否则返回false。

def anagram(string1,string2): 
# Converting the string into lists 
   lst1 = list(string1) 
   lst2 = list(string2) 
# Sorting the list value 
   lst1.sort() 
   lst2.sort() 
   position = 0 
   matche = True

   while position < len(string1) and matche: 
      if lst1[position]==lst2[position]: 
         position = position + 1 
      else: 
         matche = False 
      return matche 
print(anagram('Coding','dingoC'))

输出

True

使用原生方法

原生的方法是创建每个可能的子集，然后从包含相同大小和互为变位词的字符串的最大大小的子集开始迭代。该方法的时间复杂度为O((2^n)m)，其中n和m分别是数组和字符串的大小。

示例

以下是使用原生方法查找变位词的最大子集的大小的示例:

def anagram(array, n) :
   maximumSize = 0 
   count = {} 
   for i in range(s) : 
      # sorting the string array[i] = ''.join(sorted(array[i]))
      # Incrementing the count of the string 
      if array[i] in count :
         count[array[i]] += 1 
      else : 
         count[array[i]] = 1 

      # Computing the maximum size of the strings 
      maximumSize = max(maximumSize, count[array[i]]) 
   return maximumSize 

# The driver code array = [ "Facebook", "bookecFa", "Twitter", "ceaFkoob", "School" ] 
s = len(array) 
print('The largest size of anagram is :', anagram(array, s)) 
arrayA = [ "hot", "cold", "toh", "dolc", "rat", "mice"] 
s = len(arrayA) 
print('The largest size of anagram is :', anagram(arrayA, s))

输出

以下是上述代码的输出 –

The largest size of anagram is : 3 
The largest size of anagram is : 2

示例

最好的方法是存储每个单词的频率数组。在这种情况下，我们只需迭代单词的字母并增加当前字母的频率。只增加相同频率数组 [] 的数量，然后选择最大的值。这种策略只适用于字符串长度与数组大小的最大值相对应的情况。

def anagram(array, n) : 
   maximumSize = 0 
   # Initializing the dictionary of array 
   count = {} 
   for i in range(s) : 
      # list to store the frequency of element 
      frequency=[0 for i in range(28)] 
      for char in array[i]: 
         frequency[ord(char) - ord('b')] += 1 
      # Incrementing the count of the frequency array in the dictionary 
      temp = "".join(str(i) for i in frequency) 
      if temp not in count: 
         count[temp] = 1
      else: 
         count[temp] += 1 
      # Computing the maximum size 
      maximumSize = max(maximumSize, count[temp]) 

   return maximumSize 
# The driver code 
array = [ "Facebook", "bookecFa", "Twitter", "ceaFkoob", "School" ] 
s = len(array) 
print('The largest size of anagram is :', anagram(array, s)) 
arrayA = [ "hot", "cold", "toh", "dolc", "rat", "mice"] 
s = len(arrayA) 
print('The largest size of anagram is :', anagram(arrayA, s))

输出

以下是上述代码的输出结果 –

The largest size of anagram is : 3 
The largest size of anagram is : 2

使用counter()方法

输入字符串中的单词通过空格分隔。字符串列表中的每个字符串被排序。使用counter方法，建立一个以字符串为键，频率为值的字典。利用max函数获得频率的最大值。

示例

以下是使用counter()方法找到变位词最大子集大小的示例 –

from collections import Counter 
def anagram(string1): 
   # splitting input string separated by the space 
   string1 = string1.split(" ")

   # sorting each string in the given list of strings 
   for i in range(0,len(string1)): 
      string1[i]=''.join(sorted(string1[i])) 

# creating the dictionary using counter method having strings as key and their frequencies as values 
   newstring1 = Counter(string1)

   # getting the maximum value of the frequency 
   print ("The Size Of the largest subset of the Anangram word is ::>",max(newstring1.values())) 
      # The driver program 
   if __name__ == "__main__": 
      string1 = input("Enter any string ::>") 
anagram(string1)

输出

以下是上述代码的输出结果 –

Enter any string ::>"Facebook", "bookecFa", "Twitter", "ceaFkoob", "School" 
The Size Of the largest subset of the Anangram word is ::> 3