Python program to Check all strings are mutually disjoint
Given a string list, our task is to write a Python Program to check all strings are disjoint from one another.
Example:
Input : test_list = [“gfg”, “is”, “bet”]
Output : True
Explanation : No string character repeat in other strings.Input : test_list = [“gfg”, “is”, “best”]
Output : False
Explanation : s repeats in both “is” and “best”, hence false.
Method #1 : Using any() + intersection() + enumerate()
In this, we perform the task of getting common elements using intersection(), and the intersection is performed between all combinations of strings with each other using enumerate() and any() is used to test if any string has any character present in other string.
Python3
# Python3 code to demonstrate working of # Test if all strings are mutually disjoint # Using any() + intersection() + enumerate() # initializing list test_list = [ "gfg" , "is" , "bet" ] # printing original list print ( "The original list is : " + str (test_list)) # performing intersection of each string with every other res = not any ( set ( list (sub1)).intersection( set ( list (sub2))) for idx, sub1 in enumerate (test_list) for sub2 in test_list[idx + 1 :]) # printing result print ( "Are strings mutually disjoint? : " + str (res)) |
Output:
The original list is : ['gfg', 'is', 'bet'] Are strings mutually disjoint? : True
Time Complexity: O(n2)
Auxiliary Space: O(n)
This problem can be solved by matching the concatenated string lengths and checking for equality of lengths of strings and converted set. Fails in case in which is similar string contains duplicate elements.
Python3
# Python3 code to demonstrate working of # Test if all strings are mutually disjoint # Using # initializing list test_list = [ "gfg" , "is" , "bet" ] # printing original list print ( "The original list is : " + str (test_list)) # performing concatenation and checking # for lengths concats = ''.join(test_list) res = len (concats) = = len ( set (concats)) # printing result print ( "Are strings mutually disjoint? : " + str (res)) |
Output:
The original list is : ['gfg', 'is', 'bet'] Are strings mutually disjoint? : False
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #3 : Using Counter() function
Python3
# Python3 code to demonstrate working of # Test if all strings are mutually disjoint from collections import Counter # initializing list test_list = [ "gfg" , "is" , "best" ] # printing original list print ( "The original list is : " + str (test_list)) concats = "" for i in test_list: freq = Counter(i) concats + = ''.join( list (freq.keys())) res = len (concats) = = len (Counter(concats)) # printing result print ( "Are strings mutually disjoint? : " + str (res)) |
The original list is : ['gfg', 'is', 'best'] Are strings mutually disjoint? : False
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #4 : Using numpy unique()
Python3
import numpy as np # initializing list test_list = [ "gfg" , "is" , "bet" ] # printing original list print ( "The original list is : " + str (test_list)) # create array from list arr = np.array( list ("".join(test_list))) # using numpy to get unique elements # checking unique elements length and list length res = len (np.unique(arr)) = = len (arr) # printing result print ( "Are strings mutually disjoint? : " + str (res)) |
Output:
The original list is : ['gfg', 'is', 'bet'] Are strings mutually disjoint? : True
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #5: Using a nested loop and a flag variable
This method involves using two nested loops to compare each string with every other string in the list. A flag variable is used to keep track of whether there is any common character between two strings. If any two strings have a common character, the flag is set to True and the loops are broken. If the flag remains False, it means that all the strings are mutually disjoint.
Python3
# Python3 code to demonstrate working of # Test if all strings are mutually disjoint # Using nested loops and a flag variable # initializing list test_list = [ "gfg" , "is" , "bet" ] # printing original list print ( "The original list is : " + str (test_list)) # performing intersection of each string with every other flag = False for i in range ( len (test_list)): for j in range (i + 1 , len (test_list)): if set (test_list[i]) & set (test_list[j]): flag = True break if flag: break # printing result print ( "Are strings mutually disjoint? : " + str ( not flag)) |
The original list is : ['gfg', 'is', 'bet'] Are strings mutually disjoint? : True
Time complexity: O(n^2), where n is the length of the input list.
Auxiliary space: O(1), which is constant.
Method #6: Using Counter and sets
- Import the Counter class from the collections module.
- Define a test_list with some strings.
- Convert the list of strings into a single string using the join() method and assign the result to the joined variable.
- Create a Counter object from the joined string using the Counter() method and assign it to the char_count variable.
- Set a flag variable to False.
- Check if the length of the Counter object is equal to the length of the joined string. If they are equal, it means that all characters in the joined string are unique, so set the flag variable to True.
- Print the result of the flag variable, which will be True if the strings are mutually disjoint, and False otherwise.
Python3
from collections import Counter test_list = [ "gfg" , "is" , "bet" ] # printing original list print ( "The original list is : " + str (test_list)) joined = "".join(test_list) char_count = Counter(joined) flag = False if len (char_count) = = len (joined): flag = True # printing result print ( "Are strings mutually disjoint? : " + str ( not flag)) #This code is contributed by Vinay Pinjala. |
The original list is : ['gfg', 'is', 'bet'] Are strings mutually disjoint? : True
The time complexity of the algorithm is O(n), where n is the total number of characters in all the strings in the input list. This is because the join() method takes O(n) time to concatenate all the strings in the list into a single string, and creating a Counter object from the joined string takes O(n) time as well. The loop that checks the length of the Counter object takes O(1) time.
The auxiliary space of the algorithm is also O(n), where n is the total number of characters in all the strings in the input list. This is because the joined string and the Counter object both require O(n) space to store all the characters in the strings. The flag variable and other constant-sized variables used in the algorithm require O(1) space.
Contact Us