Python程序检查两个句子是否可以通过重新排列单词使其相同

---

在这个问题中，我们需要检查是否可以通过重新排列字符串的单词来使两个字符串相等。我们将学习三种不同的方法来解决这个问题。

在第一种方法中，我们将使用字典。在第二种方法中，我们将使用sort()方法，在第三种方法中，我们将使用counter()构造函数，该构造函数用于计算python中可散列对象的个数。

问题陈述 – 我们给定包含句子的str1和str2。我们需要检查是否可以通过重新排列字符串的单词来使这两个字符串相等。根据我们是否可以通过重新排列单词使字符串相等，打印“是”或“否”。

示例

输入– Str1 = "welcome to the tutorialspoint", Str2 = "tutorialspoint to welcome the"

输出– ‘是’

解释– 由于两个字符串都包含相同且相等的单词，因此我们可以通过重新排列单词使两个字符串相等。

输入– Str1 = ‘a b c d’ Str2 = ‘b c d e’

输出– ‘否’

解释–Str1不包含‘e’，但Str2包含它，因此我们无法通过重新排列单词使它们相等。

输入– Str1 = ‘Hello’ Str2 = ‘Hello’

输出– ‘是’

解释– 由于两个字符串已经相等，因此输出为“是”。

方法1

在这种方法中，我们将使用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)，因为我们使用字典来存储单词及其在特定字符串中的出现次数。

方法2

在这种方法中，我们将使用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)，因为我们将字符串单词存储在列表中。

方法3

在这种方法中，我们将使用counter()构造函数创建一个映射，其中单词作为键，句子中出现次数的总数作为值。如果我们通过使用counter()构造函数对两个字符串获得相同的对象，则可以重新排列字符串的单词以使它们相等。

算法

• 拆分字符串以将其转换为单词列表。

• 使用counter()构造函数并将列表作为参数传递。此外，分别将返回的对象存储在list1和list2的counter1和counter2变量中。

• 如果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()方法的方法比第一种和第三种方法具有更高的时间和空间复杂度，因为我们需要对列表进行排序。第一种和第三种方法经过优化，并且具有相同的时间和空间复杂度。此外，第三种方法的代码比第一种方法的代码更易读。