求字符串array的补集

地里看到的面筋，没有什么头绪

第二个楼主给了个hashmap的解法，但没有看懂怎么用map保存

bit吗？
tags的数量是多少？不大的话可以考虑用bit
对这些数据流tags进行编号，每个用一个bit来表示，在表示1，不在表示0
如果tags的数量不超过32个，用一个integer就能够表示，filter取补集就是对这个integer按位取反
如果tags的数量有10000个，用1000个integer就能够表示，4KB不大
对tags编号可以考虑用字典序
这是离线算法。在线算法不太好处理，需要问面试官的需求是什么

如果数据流的内容是高度相似的话，可不可以考虑用bit？我们假设所有的可能的tag只有30个(如果超过三十个考虑用一个int array或者long/long array)。
这样的话每一个set都可以用一个int表示。
拿面筋的例子为例：
apple --> 0
Facebook --> 1
google ---> 2
banana ---> 3
tesla ---> 4
intuit ----> 5
         ['apple, facebook, google', 'banana, facebook', 'facebook, google, tesla', 'intuit, google,facebook']
==>  [0000 0111, 0000 1010, 0001 0110, 0010 0110]
然后比如filter by [apple ===> mask = 0000 0001]
ret = 0
for tag in tags:
      if (mask & tag) == mask: // check if mask is a subset of tag
         ret = ret | (~mask & tag)

然后 ret 对应的index就是补集。

举个例子，key如果是facebook，{facebook: [[apple, google], [banana], [google ,tesla], [intuit, google]}

非著名农民 发表于 2023-3-30 18:17
举个例子，key如果是facebook，{facebook: [[apple, google], , [google ,tesla], }

可是我感觉这样不大方便诶，如果你input里面有两个呢，这样接下来要怎么做

Trie应该可解？

一亩仨分 发表于 2023-3-31 00:54
如果数据流的内容是高度相似的话，可不可以考虑用bit？我们假设所有的可能的tag只有30个(如果超过三十个考 ...

非常感谢这么详细的回复！感觉确实应该是这样做的～

_图图 发表于 2023-3-31 00:41
bit吗？
tags的数量是多少？不大的话可以考虑用bit
对这些数据流tags进行编号，每个用一个bit来表示，在 ...

谢谢回复！感觉是这个思路！

bloom filter

這樣不更簡單?

class Solution {
    public String[] filter(String[][] inputs, String[] filterTag) {
       Set<String> filter = new HashSet<>();
       for(String s: filterTag)
       filter.add(s);
       Set<String> res = new HashSet<>();
       for(String[] l: inputs)
       {
           Set<String> cur = new HashSet<>();
           for(String s: l)
               if(!filter.contains(s))
                   cur.add(s);
           
           if((cur.size() + filter.size()) == l.length)
               for(String s: cur)
               res.add(s);
       }
      
       String[] resa = new String[res.size()];
       int x = 0;
       for(String s: res)
           resa[x++] = s;
       return resa;
    }