Python – Nested Dictionary Subset

Given a Nested Dictionary, test if another dictionary is a subset.

Examples:

Input : test_dict = {"gfg": 12, 'best' : {1 : 3, 4 : 3, 'Lazyroar' : {8 : 7}}}, sub_dict = {8 : 7} 
Output : True 
Explanation : Required Nested dictionary present in Dictionary.

Input : test_dict = {"gfg": 12, 'best' : {1 : 3, 4 : 3, 'Lazyroar' : {8 : 7}}}, sub_dict = {9 : 7} 
Output : False 
Explanation : Nested dictionary not present in Dictionary. 

Method 1: Using all() + any() + isinstance() + recursion

In this, We check for subset at each nesting using function, and check for all the keys matching using all(), any() is used for the utility to test for any nested possible subset matching the tested subset on the test dictionary. Each nesting is tested using recursion.

Output:

The original dictionary is : {‘gfg’: 12, ‘best’: {1: 3, 4: 3, ‘Lazyroar’: {8: 7}}, ‘cs’: 7} Is dictionary subset : True

Time complexity: O(N), where N is the number of elements in the master dictionary.
Auxiliary space: O(N), as it creates multiple recursive function calls and temporary dictionaries and lists during the search. 

Method 2: Using set() method

Another approach to solving this problem is by converting the nested dictionaries into sets of tuples and then checking if the subset is present in the master dictionary using the set.issubset() method.

Step-by-step approach ;

• Define a function nested_dict_to_set(d) that takes a dictionary d as input.
  • Check if the input dictionary d is an instance of the dictionary type using the isinstance() function.
  • If d is an instance of dictionary, iterate over the key-value pairs in d using the items() method.
  • For each key-value pair in d, apply the nested_dict_to_set() function recursively to the value, and create a tuple containing the key and the result of the recursive call.
  • If d is an instance of a list, apply the nested_dict_to_set() function recursively to each item in the list using a list comprehension.
  • If d is neither a dictionary nor a list, return d as is.
• Define a function is_subset(mast_dict, subdict) that takes two dictionaries mast_dict and subdict as input.
  Inside the is_subset() function, call the nested_dict_to_set() function on both mast_dict and subdict to convert them into sets of tuples.
  • Use the all() function to check if all the items in the subdict set are present in the mast_dict set.
  • Return the result of the all() function.
• Initialize a dictionary test_dict with some nested dictionaries and values.
• Print the original dictionary test_dict.
• Initialize a subset dictionary sub_dict.
• Call the is_subset() function with test_dict and sub_dict as arguments and store the result in the res variable.
• Print the result of the is_subset() function call.

The original dictionary is : {'gfg': 12, 'best': {1: 3, 4: 3, 'Lazyroar': {8: 7}}, 'cs': 7}
Is dictionary subset : False

Time complexity: O(n), where n is the total number of elements in the input dictionaries. 
Auxiliary space: O(n), where n is the total number of elements in the input dictionary. 

Method 3: Naive (using recursion and iteration in a single function)

Here we will be checking if the sub_dict is a subset of the master_dict.

Approach:

1. Create a function called is_subset_dict that takes two arguments master_dict and sub_dict.
2. Check if the sub_dict is empty, if it is empty, then return True because an empty dictionary is always a subset of any dictionary.
3. Iterate over the keys and values of the sub_dict, and for each key-value pair:
   • a. Check if the key exists in the master_dict.
     b. If the key exists, check if the value is a dictionary or not. If it is a dictionary, then call the is_subset_dict function recursively with the corresponding sub-dictionaries.
     c. If the value is not a dictionary, compare the values of the sub_dict and master_dict.
     d. If the value is not present in the master_dict, then return False.
     e. If all the values in the sub_dict are present in the master_dict, then return True.

True
False

Time complexity: O(N*M) where N is the number of keys in the sub_dict and M is the maximum depth of the sub_dict.
Auxiliary space complexity is O(M) where M is the maximum depth of the sub_dict.

Method 4: Using the all() function and dictionary comprehension

The all() function returns True if all elements of an iterable are true. We can use this function with a dictionary comprehension to check if all key-value pairs in dict2 are also present in dict1.

Approach :

1. The function takes two dictionaries, dict1 and dict2, as inputs.
2. The function creates a boolean variable is_subset and sets it to True.
3. The function creates a dictionary comprehension that iterates over the key-value pairs in dict2. For each key-value pair (k, v) in dict2, the comprehension checks if k is a key in dict1 and if v is equal to the value of dict1[k].
4. The function passes the resulting dictionary comprehension to the all() function, which returns True if all key-value pairs in dict2 are also present in dict1.
5. If the all() function returns False, the function sets is_subset to False.
6. The function returns the value of is_subset.

True
False

Time complexity: O(len(dict2)), as the dictionary comprehension and all() function iterate over the key-value pairs in dict2.
Auxiliary space: O(1), as we only create a single boolean variable is_subset.

Method 5 : use the built-in function issuperset(). 

Step-by-step approach:

Step 1: Create two sets using the items() method on the dictionaries.

Step 2: Use the issuperset() function to check if the first set is a superset of the second set.

Step 3: Return True if the first set is a superset of the second set, False otherwise.

True
False

Time complexity: O(n), where n is the number of elements in the larger dictionary.
Auxiliary space: O(n)