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): 
# 将字符串转换为列表 
   lst1 = list(string1) 
   lst2 = list(string2) 
# 对列表进行排序 
   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) : 
      # 对字符串排序 array [i] = ''.join(sorted(array[i]))
      # 计算字符串的计数 
      if array[i] in count :
         count[array[i]] += 1 
      else : 
        count[array[i]] = 1 

      # 计算字符串的最大大小 
      maximumSize = max(maximumSize, count[array[i]]) 
   return maximumSize 

# 驱动器代码 
array = [ "Facebook", "bookecFa", "Twitter", "ceaFkoob", "School" ] 
s = len(array) 
print('最大变位词单词子集大小为：', anagram(array, s)) 
arrayA = [ "hot", "cold", "toh", "dolc", "rat", "mice"] 
s = len(arrayA) 
print('最大变位词单词子集大小为：', anagram(arrayA, s))

输出结果

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

最大变位词单词子集大小为： 3 
最大变位词单词子集大小为： 2

示例

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

def anagram(array,n):
   maximumSize = 0
   # 初始化数组的字典
   count = {}
   for i in range(n):
      # 存储元素的频率的列表
      frequency = [0 for i in range(28)]
      for char in array[i]:
         frequency[ord(char)-ord('b')] += 1
      # 在字典中增加频率数组的计数
      temp = "".join(str(i) for i in frequency)
      if temp not in count:
         count[temp] = 1
      else:
         count[temp] += 1
      # 计算最大的size
      maximumSize = max(maximumSize, count[temp])
   return maximumSize

# 主程序
array = ["Facebook","bookecFa","Twitter","ceaFkoob","School"]
s = len(array)
print('最大的anagram size是：', anagram(array, s))
arrayA = ["hot","cold","toh","dolc","rat","mice"]
s = len(arrayA)
print('最大的anagram size是：',anagram(arrayA, s))

输出

以下是上述代码的输出 –

最大的anagram size是：3
最大的anagram size是：2

使用counter()方法

输入字符串中的单词以空格分隔。对字符串列表中的每个字符串进行排序。使用counter方法，建立一个字典，其中字符串为键，出现频率为值。利用max函数获取频率的最大值。

例子

以下是使用counter()方法查找最大的anagram单词子集的大小的示例 –

from collections import Counter

def anagram(string1):
   # 以空格分隔输入字符串
   string1 = string1.split(" ")
   # 对给定字符串列表中的每个字符串进行排序
   for i in range(0,len(string1)):
      string1[i] = ''.join(sorted(string1[i]))
   # 使用counter方法创建具有字符串作为键和它们的频率作为值的字典
   newstring1 = Counter(string1)
   # 获取频率的最大值
   print("最大的anagram子集大小为：", max(newstring1.values()))

# 主程序
if __name__=="__main__":
   string1 = input("输入任何字符串：")
   anagram(string1)

输出

以下是上述代码的输出 –

输入任何字符串："Facebook", "bookecFa", "Twitter", "ceaFkoob", "School"
最大的anagram子集大小为：3