javascript - 减少字符串数组以使其没有重复项或子字符串

Question

给定一个数组

['/a','/a/b/c/d/e','/b','/b/c','/a/b/c/d','/a','/b']

我希望能够将该数组减少到:

['/a/b/c/d/e','/b/c'] 

即每个唯一路径中最长的一条('/a' 是 '/a/b/c/d/e' 的子字符串)

也许我不知道正确的术语，但我已经在谷歌上搜索了几个小时，但一无所获

我正在考虑按元素长度排序，然后为每个元素循环遍历列表，检查 indexOf() 直到到达元素本身

就是看起来有点贵。

编辑我解释得不够好 - 字符串是路径 - 我需要使用 mkdirp 来创建目录结构，但不想多次调用它( mkdir/a/b/c/d/e 将创建/a/b/c ，所以如果我有另一个路径/a/b/c 我只想忽略它

Answer 1

我会对数组进行排序。然后，迭代。对于每个元素，如果它等于下一个元素或其子字符串，则跳过它。否则，将其添加到动态增长的结构中。最后，将动态增长的结构转换为数组。

您只需检查下一项，因为任何其他内容的前缀都会按字母顺序出现在它之前，就在使用它作为前缀的最短字符串之前。这会将您的算法缩减为 O(nlgn)。

幸运的是，“/”位于 ASCII 中的字母和数字之前，这将帮助您将其扩展到具有多字母文件夹名称的路径。

假设您的原始数组位于 arr 中。

var arr = ['/a','/a/b/c/d/e','/b','/b/c','/a/b/c/d','/a','/b'];
arr.sort();
var output = [];
for(var i = 0; i < arr.length; i++)
{
  if(i < arr.length - 1 && arr[i + 1].indexOf(arr[i]) == 0 &&
    (arr[i].length == arr[i + 1].length || arr[i + 1].charAt(arr[i].length) == "/"))
  {
    continue;
  }
  output.push(arr[i]);
}
console.log(output);

在 for 循环中，对于每个字符串，我们检查数组中是否有另一个字符串在其后面；如果不是，则该字符串不是另一个路径的前缀。然后，我们检查当前字符串和下一个字符串是否相等。如果不是，我们检查下一个字符串是否以当前字符串开头，并且当前字符串之后的下一个字符是否是下一个字符串中的“/”，这样我们就不会假设“abc/def”是以下字符串的前缀“abc/defghi/jkl”，这显然是两个独立的路径。