当前位置：极客教程 > Python 实例 > Python 程序 > Python程序：查找变位词单词最大子集的大小

Python程序：查找变位词单词最大子集的大小

Python程序：查找变位词单词最大子集的大小

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

要成为变位词，重新排列的字符串或数字的每个字符还必须是另一个字符串或数字的组成部分。换句话说，如果第二个字符串刚好是第一个字符串重新排列的结果，那么一个字符串就被称为另一个字符串的变位词。例如，单词“The program”和“rogPrma”是变位词，单词“Code”和“doCe”也是。

输入-输出情景

让我们以一个输入和输出情景为例，来查找最大变位词单词的子集大小。

Input: Facebook bookecFa Twitter ceaFkoob School 
Outpu: 3
Python

在给定的输入中，只有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'))
Python

输出结果

True
Python

使用朴素方法

朴素方法是创建每种可能的子集，然后从包含所有相同大小和变位词的字符串的子集的最大大小开始迭代。该方法的时间复杂度为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))
Python

输出结果

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

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

示例

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

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))
Python

输出

以下是上述代码的输出 –

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

使用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)
Python

输出

以下是上述代码的输出 –

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

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

登录

找回密码？

注册