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()方法的方法比第一種和第三種方法具有更高的時間和空間複雜度，因為我們需要對列表進行排序。第一種和第三種方法經過最佳化，並且具有相同的時間和空間複雜度。此外，第三種方法的程式碼比第一種方法的程式碼更易讀。