二维数组中如何去除有被其他数组元素包含的元素

[einq7]

// 输入
const data = [
  ["root", "system", "synchronization-logs"],
  ["root", "system", "synchronization-configs"],
  ["root", "system"],
  ["root", "configs"],
  ["root"],
];

// 期望输出
const output = [
  ["root", "system", "synchronization-logs"],
  ["root", "system", "synchronization-configs"],
  ["root", "configs"],
]

小弟在线求指导

[QingchuanZhang]

按照数组长度从大到小，每次看是不是之前数组的子集

[crclz]

笨办法

[musi]

`
data.filter((value, index, arr) => !arr.some((a, idx) => index != idx && value.every(val => a.includes(val))))
`

[einq7]

@musi 厉害，，对比自己之前写的一坨，自己差了好多

[SakuraSa]

创建前缀树，然后再遍历叶子节点输出路径？时间复杂度 O(n)空间复杂度 O(n)

[SakuraSa]

```js
const data = [
["root", "system", "synchronization-logs"],
["root", "system", "synchronization-configs"],
["root", "system"],
["root", "configs"],
["root"],
];


function filter_file_path(path_list) {
// build perfixes tree
let root = {'__size__': 0};
data.forEach(path => {
var state = {'node': root};
path.forEach(part => {
if (state.node[part] === undefined) {
state.node[part] = {'__size__': 0};
state.node.__size__ ++;
}
state.node = state.node[part];
});
});

// filter out non-leaf node path
return data.filter(path => {
var state = {
'node': root
};
path.forEach(part => {
state.node = state.node[part];
});
return state.node.__size__ === 0;
});
}

console.log(filter_file_path(data));
```

[einq7]

@SakuraSa 感谢分享！我去看看

[VDimos]

排序加哈希编码？

[lithbitren]

数据量不大的话就暴力 includes，时间复杂度最优应该还是前缀树

[AboveYunhai]

@SakuraSa @einq7 前缀树代码有些 bug 和部分情况没有处理，而且可以在建立前缀树的时候同时对数据进行处理，这样数据只需要走一遍了，只修改了一点同时减少了代码量。

```js
function filter_file_path(path_list) {
// build perfixes tree
let root = {'__size__': 0};
var output = [];
path_list.forEach(path => {
var state = {'node': root};
var update = false;
path.forEach(part => {
if (state.node[part] === undefined) {
update=true;
state.node[part] = {'__size__': 0};
state.node.__size__ ++;
}
state.node = state.node[part];
});
//new tree, add to output list
if(update === true) {
output.push(path);
update=false;
}
});
return output;
}
```