Python Program to check if two sentences can be made the same by rearranging the words
Given two strings S1 and S2 representing two sentences, the task is to check if two sentences can be made same by rearranging the words of any of the strings.
Examples:
Input: S1 = “please select a category”, S2 = “category a please select”
Output: YesInput: S1 = “hello world this is python language”, S2 = “python language is this modern world”
Output: No
Explanation: The word “hello” does not exist in the second string.
- Store the words of the strings S1 and S2 in separate lists, say list1[] and list2[], respectively.
- Sort both the lists in ascending order.
- If both the lists are found to be equal, print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
Python3
# Python implementation # of the above approach # Function to check if two sentences # can be made same by rearranging words def ReArrangeStrings(string1, string2): # Stores the words of the # sentences in separate lists list1 = list (string1.split()) list2 = list (string2.split()) # Sort both the strings list1.sort() list2.sort() # If two lists are equal if (list1 = = list2): return True else : return False # Driver Code # Input S1 = "please select a category" S2 = "category please a select" # Function call to check if two sentences # can be made same by rearranging words if (ReArrangeStrings(S1, S2)): print ( "Yes" ) else : print ( "No" ) |
Yes
Time Complexity: O(N* M* log(N)), where M is the length of the longest strings.
Auxiliary Space: O(N)
Approach using Counter() and split() built-in Functions: Follow the steps to solve the problem:
- Store the words of the strings S1 and S2 in separate lists, say list1[] and list2[], respectively.
- Count the words present in the strings S1 and S2 using the Counter() function and store it in separate variables, say counter1 and counter2 respectively.
- Check if counter1 is equal to counter2 or not. If found to be true, print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
Python3
# Python implementation # of the above approach # Import counter function # from collections from collections import Counter # Function to check if two sentences # can be made same by rearranging words def ReArrange(S1, S2): # Store the words of the # strings in separate lists list1 = list (S1.split()) list2 = list (S2.split()) listcounter1 = Counter(list1) listcounter2 = Counter(list2) # If counter of both the # sentences are same if (listcounter1 = = listcounter2): return True else : return False # Driver Code # Input S1 = "please select a category" S2 = "category please a select" # Function call to check if two # sentences can be made same # by rearranging words if (ReArrange(S1, S2)): print ( "Yes" ) else : print ( "No" ) |
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach: using operator.countOf() method
Python3
# Python implementation # of the above approach import operator as op # Function to check if two sentences # can be made same by rearranging words def ReArrange(S1, S2): # Store the words of the # strings in separate lists list1 = list (S1.split()) list2 = list (S2.split()) for i in list1: if op.countOf(list1, i) ! = op.countOf(list2, i): return False return True # Driver Code # Input S1 = "please select a category" S2 = "category please a select" # Function call to check if two # sentences can be made same # by rearranging words if (ReArrange(S1, S2)): print ( "Yes" ) else : print ( "No" ) |
Yes
Time Complexity: O(N)
Auxiliary Space : O(N)
Approach: Using a dictionary to count occurrences of words in both sentences:
Algorithm :
- Split the two input strings into separate lists of words.
- Initialize two empty dictionaries, count1 and count2, to keep track of the count of each word in the two lists.
- Loop over each word in list1 and update the count in count1.
- Loop over each word in list2 and update the count in count2.
- Check if count1 and count2 are equal. If they are, return True. Otherwise, return False
Python3
def ReArrange(S1, S2): list1 = S1.split() list2 = S2.split() count1 = {} count2 = {} for word in list1: count1[word] = count1.get(word, 0 ) + 1 for word in list2: count2[word] = count2.get(word, 0 ) + 1 return count1 = = count2 S1 = "please select a category" S2 = "category please a select" if ReArrange(S1, S2): print ( "Yes" ) else : print ( "No" ) #This code is contributed by Jyothi Pinjala. |
Yes
The time complexity : O(n), where n is the total number of words in the two input strings. This is because the loop over the words in list1 and list2 each take O(n) time, and the dictionary operations take constant time.
The space complexity : O(k), where k is the total number of unique words in the two input strings. This is because the dictionaries count1 and count2 each have at most k key-value pairs, where k is the number of unique words in the two lists. The lists list1 and list2 also each have k elements, but this does not contribute to the space complexity since we are only counting the unique words.