0

I have two lists of strings:

a = ['ab','ac','ad',..., 'aba','abc',...] # n = 10000 of unique strings
b = ['ab', 'ac', ..., 'ab']               # m = 100 have duplicates
c = []

How to find common string between these two strings? My solution runs in m*n complexity (right?):

    for i in a:
        if i in b:
            c.append(i)

is there a way to solve it in O(m) time complexity?

Tolegen Azamat
  • 29
  • 1
  • 8

2 Answers2

2

since the value in a are unique, so you can create a dict, in O(n), to access and check that element in O(1).

Iterate through b and check each element of b with dict in O(1), it will save time then using set operation and also include if there are same multiple same element present in b and in a also

a = ['ab','ac','ad', 'aba','abc'] # n = 10000 of unique strings
b = ['ab', 'ac', 'ab', 'kk']               # m = 100 have duplicates
c = []


a_dic = {i:1 for i in a}
sol = []

for i in b:
    if a_dic.get(i, None):
        sol.append(i)
sahasrara62
  • 10,069
  • 3
  • 29
  • 44
0

You can convert your lists to set and do a intersection on them using &:

>>> a = ['ab','ac','ad','aba','abc']
>>> b = ['ab', 'ac', 'ab']

>>> set(a) & set(b)
{'ab', 'ac'}

Set Intersection returns elements which are common in both the sets. But note: Since set are unordered, you won't be able to maintain the order from list a or b if that's needed.

Here's a functional approach to achieve the same using set.intersection() method:

>>> set(a).intersection(b)
{'ac', 'ab'}
Moinuddin Quadri
  • 46,825
  • 13
  • 96
  • 126
  • @TolegenAzamat Did this answer and [sahasrara62 's answer](https://stackoverflow.com/a/65936319/2063361) helped you? If yes, please upvote the answers by hitting the "up" arrow on the left of the answers. You can also mark the best answer as accepted by hitting "tick" icon. It helps answerer with reputation gain of +10 for each upvote and +15 for accepted answer – Moinuddin Quadri Feb 07 '21 at 16:16