資料結構
網路
關係資料庫管理系統 (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 次瀏覽
