How to connect elements in two different sets?

Question

If there are two sets -

set1 - [tag, boLD, Link]
set2 - [BOLd, TAG, Badge, foo]

What can be an effective algorithm for creating pairs of elements of type -

pairs = [tag, TAG], [boLD, BOLd], [Link, null], [null, Badge], [null, foo]

Note that pairing is based on names case-insensitive.

I want to avoid O (N ^ 2), which scans all the elements in set1 iteratively and scans the element in set2.

EDIT: I think that if we can use Ternary Search Triesto make an implementation of a character table, where the keys are elements from set1 and values ​​from set2. set2 remaining elements can be processed finally.

Answer 1

O(n), , O(1) get - HashMap.

    HashMap<String, String> set1 = new HashMap<>();
    HashMap<String, String> set2 = new HashMap<>();
    class Pair{
        String str1;
        String str2;

        Pair(String s1, String s2){
            str1 = s1;
            str2 = s2;
        }
    }
    Set <Pair> pairs = new HashSet<>();
    set1.put("tag", "tag");
    set1.put("bold", "boLD");
    set1.put("link", "Link");
    set2.put("tag", "TAG");
    set2.put("bold", "BOLd");
    set2.put("badge", "Badge");
    set2.put("foo", "foo");

    for (String s : set1.keySet()){
        if (set2.containsKey(s))
            pairs.add(new Pair(set1.get(s), set2.get(s)));
        else
            pairs.add(new Pair(set1.get(s), null));
    }

    for (String s : set2.keySet()){
        if (!set1.containsKey(s))
            pairs.add(new Pair(null, set2.get(s)));
    }

    for(Pair p : pairs)
        System.out.println(p.str1 + " " + p.str2);

Answer 2

HashMap . . .

Answer 3

( Python, Java ), , :

map1 = {}
for i,e in enumerate(set1):
    s = e.lower()
    map1[s] = i

map2 = {}
for i,e in enumerate(set2):
    s = e.lower()
    map2[s] = i

pairs = []
for i,e in enumerate(set1):
    s = e.lower()
    if s in map2:
        elem = (e, set2[map2[s]])
    else:
        elem = (e, None)
    pairs.append(elem)

for i,e in enumerate(set2):
    s = e.lower()
    if s not in map1:
        pairs.append((None, e))

, , .. 0 1 , , .

This is probably not the most efficient way to get around this, but it seems to be alright as it is still O (n).