CODEWITHSUNDEEP
python
Ira
Ira

Reputation: 567

How to extract the corresponding key whose value contains the item from a list?

I have a list and a dictionary. For each item in the list, i want to retrieve the key in the dictionary whose value contains that item.

I tried writing the code that takes an item from the list and loops through the dictionary each time to see if the value contains that item and return the key. I think this would be O(n2) complexity.

my_list = ['1.1.1.1','2.2.2.2','3.3.3.3']
my_dict = {
            1234 : '4.4.4.4,5.5.5.5,2.2.2.2',
            4567 : '6.6.6.6,7.7.7.7,1.1.1.1',
            8910 : '8.8.8.8,9.9.9.9,3.3.3.3'
            }

def get_key(my_list, my_dict):

    for item in my_list:
        for key, value in my_dict.items():
            temp_list = []
            temp_list = value.split(',')
            if item in temp_list:
                print(key)

get_key(my_list, my_dict)

Output:
4567
1234
8910

For the item 2.2.2.2, the key 1234 should be returned and so on.

Is there a more optimized way to achieve this?

Upvotes: 1

Views: 127

Answers (2)

MisterMiyagi
MisterMiyagi

Reputation: 51989

Since you are looking for exact matches, you can invert the dictionary to search through. Conversion is O(n) once, but lookup is O(1) afterwards.

inverse = {
    value: key
    for key, values in my_dict.items()
    for value in values.split(',')
}

Given this inverted structure, you can directly look up the keys from your list:

for item in my_list:
    print(inverse[item])

Both the inversion and lookup for all items is O(n). Since the loops are not nested, the total complexity stays at O(n) total.

Upvotes: 2

shubham
shubham

Reputation: 513

you can use:

my_list = ['1.1.1.1','2.2.2.2','3.3.3.3']
my_dict = {
        1234 : '4.4.4.4,5.5.5.5,2.2.2.2',
        4567 : '6.6.6.6,7.7.7.7,1.1.1.1',
        8910 : '8.8.8.8,9.9.9.9,3.3.3.3'
        }
result = []
for i in my_dict:
    s = list(set(my_dict.get(i).split(',')).intersection(my_list))
    result.insert(my_list.index(s[0]),i)
print(result)

you will get the output like this

[4567, 1234, 8910]

Upvotes: 0

Related Questions