数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学查找最大回文词子集大小的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
343 次浏览
