javascript - 按最长公共(public)起始子串对数组元素进行分组

Question

如何根据最长的公共(public)字符串对公共(public)子串进行分组。它指的是Group strings by longest common starting substring

Alex Shevchenko 提供了一段非常好的代码，但在某些情况下它无法正常工作。添加到 var data 值 apple iphone 65 使数据看起来像:

var data = ['apple iphone 65', 'apple ipad mini 32gb', 'apple ipad mini 64gb', 'apple ipad air 64gb', 'apple ipad air 32gb', 'panasonic gh4', 'samsung s2 galaxy', 'samsung s2 galaxy red', 'samsung s3 galaxy'];

下面是预期的结果。

result = {
 "apple": [
     "apple iphone 65"
 ],
 "apple ipad mini": [
     "apple ipad mini 32gb",
     "apple ipad mini 64gb"
 ], ...;

下面是我实际得到的。

result = {
 "apple": [
     "apple iphone 65",
     "apple ipad mini 32gb"
 ],
 "apple ipad mini": [
     "apple ipad mini 64gb"
 ],
 "apple ipad air": [
     "apple ipad air 64gb",
     "apple ipad air 32gb"
 ],
 "panasonic gh4": [
     "panasonic gh4"
 ],
 "samsung s2 galaxy": [
     "samsung s2 galaxy",
     "samsung s2 galaxy red"
 ],
 "samsung s3 galaxy": [
     "samsung s3 galaxy"
 ]
};

我无法找出我的代码中的错误所在。

Answer 1

我不确定我的解决方案的效率如何，特别是如果/当数据集大小增加时，但我认为它非常接近您正在寻找的内容。

var data = ['apple iphone 65gb', 'apple ipad mini 32gb', 'apple ipad mini 64gb', 'apple ipad air 64gb', 'apple ipad air 32gb', 'panasonic gh4', 'samsung s2 galaxy', 'samsung s2 galaxy red', 'samsung s3 galaxy']

let i = 0
let obj = {}

function checkArrays(arrA, arrB) {
  let index
  for (let i = 0; i < arrA.length; i++) {
    if (arrA[i] !== arrB[i]) return index = i
  }
  return index;
}

const refineArr = (data) => {
  arr = []
  for (let i = 0; i < data.length; i++) {
    let one = data[i].split("")
    let two = data[i + 1] ? data[i + 1].split("") : data[i + 1]
    if (two) {
      let x = checkArrays(one, two)

      var index1, index2

      one.forEach((y, e) => {
        if (y === " " && e >= x) {
          return index1 = e
        }
      })

      if (!arr.includes(one.slice(0, index1).join("").trim()) &&
        !arr.includes(one.slice(0, index2).join("").trim())) {
        arr.push(one.slice(0, index1).join("").trim())
      }

      two.forEach((y, i) => {
        if (y === " " && i >= x) {
          return index2 = i
        }
      })

      if (!arr.includes(two.slice(0, index2).join("").trim()) &&
        !arr.includes(two.slice(0, index1).join("").trim())) {
        arr.push(two.slice(0, index2).join("").trim())
      }
    }
  }
  var newArr = [...new Set(arr)]
  generateObject(newArr)
}

const generateObject = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    if (!obj[arr[i]]) {
      obj[arr[i]] = data.filter((x) => {
        return x.includes(arr[i])
      })
    }
  }
  console.log(obj)
}

refineArr(data)

.as-console-wrapper { top: 0; max-height: 100% !important; }

首先，我尝试优化原始数组以仅包含要包含的键。当我遍历 data 时，我在每个索引处拆分字符串(以及下一个索引，只要定义了 i+1 处的项目)。然后我将这两个数组传递给 checkArrays，在那里我比较每个字符，然后返回它们不再相同的索引。

示例:apple ipad mini ... 作为数组是

["a", "p", "p", "l", "e", "", "i", "p", "a", "d", "", "m", "i", "n", "i", ...]

和apple ipad air...作为一个数组是

["a", "p", "p", "l", "e", "", "i", "p", "a", "d", "", "a", "i", "r",...]

它们不再相似的索引是 11。

然后我需要找到它们不同的索引(对于两者)，加上下一个空格，因为我想确保我将数组切成一个完整的单词。因此，我寻找作为空格且索引大于差异索引的元素。

我对两个数组都这样做，因为索引会不同。

对于 ["a", "p", "p", "l", "e", "", "i", "p", "a", "d", "", "m", "i", "n", "i", ...] 它是 15。

对于 ["a", "p", "p", "l", "e", "", "i", "p", "a", "d", "", "a", "i", "r", ...] 是 14。

有一种情况，我最终会像 apple ipad m 在 apple ipad mini 之后被插入 arr 但那是因为我需要测试每个数组的两个索引(因为在第一个循环中 apple ipad mini ... 是第二个词，但在第二个循环中它是第一个词)。我用这些行对此进行了补偿:

  if (!arr.includes(one.slice(0, index1).join("").trim()) 
      && !arr.includes(one.slice(0, index2).join("").trim())){
    arr.push(one.slice(0, index1).join("").trim())
  }

和

 if (!arr.includes(two.slice(0, index2).join("").trim())
     && !arr.includes(two.slice(0, index1).join("").trim())){
    arr.push(two.slice(0, index2).join("").trim())
  }

完成后，我使用 var newArr = [... new Set(arr)] 返回了一个新数组，以确保省略任何重复的值。在这一点上，你最终会得到一个数组，如 ["apple iphone", "apple ipad mini", "apple ipad air", "panasonic", "samsung s2", "samsung s3"]。这些将是我们对象中的键。

最后，generateObject 循环遍历新数组，并实质上为包含 键的过滤项目集合分配键值。因此，对于键 apple ipad mini，您将得到一个过滤后的 ["apple ipad mini 32gb", "apple ipad mini 64gb"]

集合

同样，我认为此解决方案需要为效率而改进，但我认为它至少可以帮助您从逻辑上入手。