极客笔记Python 检查是否可以通过重新排列单词使两个句子相同
在这个问题中，我们需要检查是否可以通过重新排列字符串的单词来使两个字符串相等。我们将学习三种不同的方法来解决这个问题。
在第一种方法中，我们将使用一个字典。在第二种方法中，我们将使用sort()方法，而在第三种方法中，我们将使用counter()构造函数，该函数用于计算python中可散列对象的数量。
问题陈述： 我们已经给出了包含句子的str1和str2。我们需要检查是否可以通过重新排列字符串的单词来使两个字符串相等。根据我们是否可以通过重新排列单词使字符串相等，打印“Yes”或“No”。
示例
输入： Str1 =“欢迎来到tutorialspoint”，Str2 =“tutorialspoint欢迎来到”
输出： ‘Yes’
解释： 由于两个字符串都包含相同且相等的单词，我们可以通过重新排列单词使两个字符串相等。
输入： Str1 =‘a b c d’，Str2 =‘b c d e’
输出： ‘No’
解释： Str1不包含‘e’，但是Str2包含它，所以我们不能通过重新排列单词使它们相等。
输入： Str1 =‘Hello’，Str2 =‘Hello’
输出： ‘Yes’
解释： 由于两个字符串已经相等，所以我们的输出是‘Yes’。
方法一
在这个方法中，我们将使用Python字典来存储两个字符串中每个单词的出现次数之和。然后，我们将比较两个字典来得到输出。
步骤
- 使用split()方法和list()构造函数将字符串转换为单词列表。
- 使用空字典初始化words1和words2。
- 使用get()方法获取当前单词键的存储值，并通过添加1来更新新值。
- 返回words1 words2的结果。如果words1和words2相等，则两个字符串包含相同数量的相等单词。
示例
# function to check if two sentences can be made the same by rearranging words
def reArrangeWords(string1, string2):
# Using the split() function to break the sentence into a list of words
list1 = list(string1.split())
list2 = list(string2.split())
# defining empty dictionaries to store the frequency of each word
words1 = {}
words2 = {}
# using get() to store the frequency of each word in a dictionary
for word in list1:
words1[word] = words1.get(word, 0) + 1
for word in list2:
words2[word] = words2.get(word, 0) + 1
# If both the dictionaries are equal, then the sentences can be made the same by rearranging words
return words1 == words2
# Input
Str1 = "welcome to the tutorialspoint"
Str2 = "tutorialspoint to welcome the"
# Function call
if (reArrangeWords(Str1, Str2)):
print("Yes, both the sentences can be made same by rearranging words")
else:
print("No, both the sentences cannot be made same by rearranging words")
输出
Yes, both the sentences can be made same by rearranging words
时间复杂度 – O(N)，因为我们遍历两个字符串。
空间复杂度 – O(N)，因为我们使用字典来存储特定字符串中的单词及其出现次数。
方法二
在这种方法中，我们将使用sort()方法对列表进行排序。然后，我们将比较两个列表，如果它们相等，我们可以重新安排单词使两个字符串相同。
步骤
- 使用split()方法将字符串转换为列表
-
使用sort()方法依次对list1和list2进行排序
-
如果list1和list2相等，返回true。否则，返回false。
示例
def reArrangeWords(string1, string2):
# Using the split() function to break the sentence into a list of words
list1 = list(string1.split())
list2 = list(string2.split())
# sort the list of words
list1.sort()
list2.sort()
# If all words are the same, then the sentences can be made the same by rearranging words
if (list1 == list2):
return True
else:
return False
Str1 = "welcome to the tutorialspoint"
Str2 = "tutorialspoint to welcome the"
# Function call
if (reArrangeWords(Str1, Str2)):
print("Yes, both the sentences can be made same by rearranging words")
else:
print("No, both the sentences cannot be made same by rearranging words")
输出
Yes, both the sentences can be made same by rearranging words
时间复杂度 – O(N*logN)，因为我们对两个列表进行排序。
空间复杂度 – O(N)，因为我们将单词字符串存储在列表中。
方法三
在这种方法中，我们将使用counter()构造函数创建一个包含单词作为键和它们在句子中出现总次数的映射。如果我们使用counter()构造函数为两个字符串获取相同的对象，我们可以重新排列字符串的单词使它们相等。
步骤
- 将字符串分割为单词列表。
-
使用counter()构造函数并将列表作为参数传递。还将返回的对象分别存储在counter1和counter2变量中，分别对应于list1和list2。
-
如果counter1和counter2相同，则返回true，否则返回false。
示例
from collections import Counter
def reArrangeWords(string1, string2):
# Using the split() function to break the sentence into a list of words
list1 = list(string1.split())
list2 = list(string2.split())
# sort the list of words
Counter1 = Counter(list1)
Counter2 = Counter(list2)
# If both sentences have the same set of words, return true. Else return false.
if (Counter1 == Counter2):
return True
else:
return False
# Input
Str1 = "Hey how are you"
Str2 = "Hey how you are"
# Function call
if (reArrangeWords(Str1, Str2)):
print("Yes, both the sentences can be made same by rearranging words")
else:
print("No, both the sentences cannot be made same by rearranging words")
输出
Yes, both the sentences can be made same by rearranging words
时间复杂度 – O(N) ，因为我们使用了split()方法和counter()构造函数。
空间复杂度 – O(N) ，因为我们在分割后将一个字符串存储到一个列表中。
我们已经看到了解决给定问题的三种方法。使用sort()方法的第二种方法比第一种和第三种方法有更高的时间和空间复杂度，因为我们需要对列表进行排序。第一种和第三种方法是优化的，并且具有相同的时间和空间复杂度。此外，第三种方法的代码比第一种方法的代码更易读。