Python | Substring Key match in dictionary

Sometimes, while working with dictionaries, we might have a use case in which we are not known the exact keys we require but just a specific part of keys that we require to fetch. This kind of problem can arise in many applications. Let’s discuss certain ways in which this problem can be solved. 

Method #1 : Using items() + list comprehension The combination of above method can be used to perform this particular task in which we just access the key value pairs using the items function and list comprehension helps in the iteration and access logic. 

The original dictionary is : {'All': 1, 'food': 4, 'have': 2, 'good': 3}
Values for substring keys : [4, 3]

Time Complexity: O(n)
Auxiliary Space: O(1)

Method #2 : Using dict() + filter() + lambda 

The combination of above functions can be used to perform this particular task. In this, the dict and filter function is used to convert the result to dictionary and query for the substring in list respectively. The lambda performs the task of accessing all key-value pairs. 

The original dictionary is : {'have': 2, 'good': 3, 'food': 4, 'All': 1}
Key-Value pair for substring keys : {'good': 3, 'food': 4}

Time complexity: O(n*n), where n is the number of key-value pairs in the dictionary.
Auxiliary space: O(n), to store the keys and values in dictionary.

Method #3: Using keys() and find() methods

The original dictionary is : {'All': 1, 'have': 2, 'good': 3, 'food': 4}
Values for substring keys : [3, 4]

Method #4: Using re.search()
This method uses the re.search() function from the re module to check if the search key is a substring of any of the keys in the dictionary. If it is, the corresponding value is added to a list.

The original dictionary is : {'All': 1, 'have': 2, 'good': 3, 'food': 4}
Values for substring keys : [3, 4]

Time complexity: O(n)
Auxiliary space: O(n) where n is the number of items in the dictionary

Method #5: Using a dictionary comprehension

Algorithm:

1. Initialize an empty list called “extended_list”
2. Append all elements from test_list1 to extended_list using the “extend()” method
3. For each list l in (test_list2, test_list3), do steps 4-5:
4. Iterate over each element in l using a for loop, and do step 5:
5. Append the element to extended_list using the “append()” method
6. Print the extended_list

The original dictionary is : {'All': 1, 'have': 2, 'good': 3, 'food': 4}
Values for substring keys : [3, 4]

Time Complexity:
The time complexity of the above algorithm is O(n*m), where n is the number of key-value pairs in the dictionary and m is the length of the search key string. In the worst case, we need to iterate through all n key-value pairs and check each key for the presence of the search key string, which takes O(m) time.

Auxiliary Space:
The auxiliary space complexity of the above algorithm is O(k), where k is the number of key-value pairs that contain the search key substring. This is because we create a new dictionary “res” with only the filtered key-value pairs that satisfy the search condition. The space required for this dictionary depends on the number of key-value pairs that contain the search key substring.

Method #6 : Using operator.contains() method

Approach

1. Initiate a for loop for traversing the dictionary keys
2. Check whether search_key is present in  each key using operator.contains() method
3. If found add them in output list
4. Display output list

The original dictionary is : {'All': 1, 'have': 2, 'good': 3, 'food': 4}
Values for substring keys : [3, 4]

Time Complexity : O(N)
Auxiliary Space : O(N)

Method #7: Using a for loop and string slicing

The original dictionary is : {'All': 1, 'have': 2, 'good': 3, 'food': 4}
Values for substring keys : [3, 4]

Time complexity: O(nm) where n is the number of keys in the dictionary and m is the length of the search key. This is because we iterate over all the keys in the dictionary and for each key we perform a string slicing operation which takes O(m) time.
Auxiliary space: O(k) where k is the number of keys in the dictionary. This is because we store the values corresponding to the substring keys in a list which can have a maximum of k elements.

Method #8:Using a reduce function:

1. Initialize the dictionary and the search key string.
2. Print the original dictionary.
3. Use the reduce function to filter the values in the dictionary based on whether the search key is a substring of the corresponding key.
4. Initialize the accumulated value to an empty list.
5. Define a lambda function that takes in two arguments: the accumulated value (a list of values) and the next key in the dictionary.
6. If the search key is a substring of the key, append the corresponding value to the accumulated list using the + operator.
7. Otherwise, return the accumulator unchanged using the else clause.
8. Pass the keys of the dictionary as the sequence of items to iterate over.
9. Pass an empty list as the initial value for the accumulator.

Print the resulting list of values that correspond to keys containing the search key substring.

The original dictionary is : {'All': 1, 'have': 2, 'good': 3, 'food': 4}
Values for substring keys : [3, 4]

Time Complexity:

The time complexity of iterating over a dictionary using the reduce function is O(N), where N is the number of keys in the dictionary.
The time complexity of checking whether a string is a substring of another string using the in keyword is O(N), where N is the length of the string being searched.
Therefore, the time complexity of this code is O(N^2), where N is the maximum length of a key in the dictionary.
Space Complexity:

The space complexity of initializing the dictionary and search key strings is O(N), where N is the number of keys in the dictionary and the length of the search key.
The space complexity of initializing the empty list used as the initial value of the accumulator is O(1).
The space complexity of using the reduce function to filter the values in the dictionary is O(N), where N is the number of keys in the dictionary.
Therefore, the space complexity of this code is O(N), where N is the maximum of the number of keys in the dictionary and the length of the search key.