java - 如何配对两个不同集合中的元素？

Question

如果有两组——

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

什么是制作成对元素的有效算法 -

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

请注意，配对是基于不区分大小写 的名称。

我想避免 O(N^2)，它迭代地查找 set1 中的所有元素，然后查看 set2 中的元素。

编辑:我认为如果我们可以使用Ternary Search Tries 来实现符号表，其中键是来自 set1 的元素，以及来自 set2 的值。 set2 剩下的元素终于可以处理了。

Answer 1

如果您使用一些支持O(1) get 操作的数据结构，您可以在 O(n) 中完成它 - 对于示例 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);