JavaScript最长子域后缀分组技巧

本文详细介绍了使用JavaScript实现最长子域后缀分组的方法，旨在帮助开发者高效地对字符串（如域名）进行分类和组织。该方案通过构建字典，利用分步算法识别字符串间的子域关系，并按照最长匹配原则进行分组，最终实现精准的层次化数据组织。文中提供JavaScript代码示例，并针对性能、子域定义及边界情况进行了注意事项说明。通过本文，你将掌握一种实用的JavaScript技巧，用于解决实际开发中遇到的字符串分组问题，提升数据处理效率。

引言与问题定义

在数据处理中，我们经常需要对字符串进行分类和组织。一个常见的需求是根据字符串的某个特定后缀来分组，并且这种分组应当遵循“最长匹配”原则。例如，给定一组域名，我们希望将它们按照最长的共同子域后缀进行归类。这意味着如果 hello.samsung.phone.com 和 lg.phone.com 都存在，并且 samsung.phone.com 和 phone.com 也是列表中的潜在分组键，那么 hello.samsung.phone.com 应该被分到 samsung.phone.com 组下，而 lg.phone.com 则分到 phone.com 组下。最终输出应是一个字典，其键是这些最长子域后缀，值是属于该后缀的原始字符串列表。

例如，对于输入 ["samsung.phone.com", "lg.phone.com", "phone.com", "camera.dsrl.nikon.com", "amd.gpu.com", "intel.cpu.com"]，我们期望的输出是：

{
  "phone.com": ["lg.phone.com", "samsung.phone.com"],
  "camera.dsrl.nikon.com": [],
  "amd.gpu.com": [],
  "intel.cpu.com": []
}

如果添加 "cpu.com"，则 intel.cpu.com 应被分组到 cpu.com 下：

{
  "phone.com": ["lg.phone.com", "samsung.phone.com"],
  "camera.dsrl.nikon.com": [],
  "amd.gpu.com": [],
  "cpu.com": ["intel.cpu.com"]
}

如果再添加 "hello.samsung.phone.com"，则 samsung.phone.com 自身成为一个分组键：

{
  "samsung.phone.com": ["hello.samsung.phone.com"],
  "phone.com": ["lg.phone.com"],
  "camera.dsrl.nikon.com": [],
  "amd.gpu.com": [],
  "cpu.com": ["intel.cpu.com"]
}

算法设计与实现

为了解决这个问题，我们可以设计一个JavaScript函数，它通过多步处理来确保字符串被正确地分组到其最长匹配的子域后缀下。这里的“子域”被定义为从第一个点号（.）之后开始的字符串部分。

核心算法步骤

1. 初始化字典： 将输入列表中的所有字符串作为字典的初始键，并为每个键分配一个空列表作为其值。这确保了即使某个字符串没有被其他字符串分组，它也能作为独立的键存在。

2. 识别直接子域关系： 遍历所有字符串对。对于每一对，如果一个字符串是另一个字符串的直接子域（即通过 substring(indexOf('.') + 1) 提取的后缀），则将父字符串添加到子域键对应的值列表中。

3. 收集所有被分组的字符串： 统计在第二步中被成功分组到某个键下的所有字符串。这些字符串是“域”，而不是最终的分组键。

4. 移除空键（非分组键）： 遍历字典。如果一个键的值列表为空，并且它本身没有作为其他字符串的子域被识别（即它没有在 mergedDomainList 中出现，或者说它不是任何其他字符串的父级），则将其从字典中删除。这一步的目的是移除那些既没有被分组，也没有作为其他字符串的子域的条目。

5. 精炼分组结果（实现“最长匹配”）： 这一步是实现“最长匹配”逻辑的关键。

   • 首先，获取当前字典中所有剩余的键（这些键是潜在的最终分组键）。
   • 然后，再次遍历字典的每个键值对。对于每个键的值列表，过滤掉那些自身也是字典中其他键的字符串。这样可以确保一个字符串只被其最长的、最具体的子域后缀所分组。例如，如果 samsung.phone.com 既可以被 phone.com 分组，也可以被 samsung.phone.com 自身（作为 hello.samsung.phone.com 的子域）分组，那么它将从 phone.com 的分组中移除，从而确保 hello.samsung.phone.com 能够通过 samsung.phone.com 获得更具体的归属。

JavaScript 实现代码

/**
 * 根据最长子域后缀对字符串列表进行分组。
 * 子域定义为从第一个点号之后开始的字符串部分。
 * @param {string[]} domList 包含域名或类似结构字符串的列表。
 * @returns {Object.} 一个字典，键为子域后缀，值为属于该后缀的字符串列表。
 */
function filterBySubdomain(domList) {
  const dict = {}; // 键: 子域后缀, 值: 对应域名的列表

  // 步骤 1: 初始化字典，所有输入字符串都作为潜在的键
  domList.forEach((el) => (dict[el] = []));

  // 步骤 2: 识别直接子域关系，将父字符串添加到子域键的值列表中
  for (let i = 0; i < domList.length; i++) {
    for (let j = 0; j < domList.length; j++) {
      if (i !== j) { // 避免自身与自身比较
        const currentString = domList[j];
        const firstDotIndex = currentString.indexOf(".");

        // 确保有至少一个点号且不是开头或结尾
        if (firstDotIndex > 0 && firstDotIndex < currentString.length - 1) {
          const subdomain = currentString.substring(firstDotIndex + 1);
          if (subdomain === domList[i]) {
            // domList[i] 是 domList[j] 的子域
            dict[domList[i]].push(domList[j]);
          }
        }
      }
    }
  }

  // 步骤 3: 收集所有被分组的字符串 (即在字典值中出现的字符串)
  let mergedDomainList = [];
  for (const [, domainList] of Object.entries(dict)) {
    mergedDomainList = [...mergedDomainList, ...domainList];
  }

  // 步骤 4: 删除那些作为键但其值列表为空，且未作为任何其他字符串子域的键
  // 注意：原始代码的这部分逻辑可能略有歧义，我们将其调整为：
  // 仅删除那些值列表为空，且其自身并非其他字符串子域的键。
  // 但根据问题描述，即使值列表为空，如果它在原始输入中，也可能需要保留作为键（如 "camera.dsrl.nikon.com" : []）。
  // 原始代码的意图是删除那些“被其他键替代”的空键。
  // 这里的实现将保留所有原始输入中作为键的字符串，除非它们被更长的子域所“吸收”。
  // 重新审视原始代码的意图：
  // `mergedDomainList.forEach((x) => { if (dict[x].length == 0) delete dict[x]; });`
  // 这一步实际上删除了那些在第一步被初始化为键，但在第二步中没有被任何其他字符串分组，
  // *并且* 它本身是某个更长字符串的子域的键。
  // 例如，如果 "samsung.phone.com" 在列表中，且 "phone.com" 也是键，
  // "samsung.phone.com" 的值列表在第二步结束后是空的。
  // 如果 "samsung.phone.com" 也是 `mergedDomainList` 的一部分 (因为它被 "hello.samsung.phone.com" 分组了)，
  // 那么它不会被删除。如果它没被分组，且它本身是某个子域，那么它会被删除。
  // 实际作用是：如果一个字符串 `X` 被 `Y` 分组（即 `X` 是 `Y` 的子域），
  // 且 `X` 在 `dict` 中作为键，但其值列表是空的，则删除 `X`。
  // 这一步是为了避免 `phone.com` 和 `samsung.phone.com` 都作为键，但 `samsung.phone.com` 的值列表是空的。
  // 让我们按照原始代码的精确逻辑来：
  const keysToDelete = [];
  for (const key of Object.keys(dict)) {
    if (dict[key].length === 0 && mergedDomainList.includes(key)) {
      keysToDelete.push(key);
    }
  }
  keysToDelete.forEach(key => delete dict[key]);


  // 步骤 5: 精炼分组结果，确保“最长匹配”原则
  const finalKeys = Object.keys(dict); // 当前字典中所有最终的键
  for (const [key, value] of Object.entries(dict)) {
    // 过滤掉值列表中那些本身也是最终键的字符串
    // 这样可以确保一个字符串只被其最长的、最具体的子域后缀所分组
    dict[key] = value.filter(function (el) {
      return !finalKeys.includes(el);
    });
  }

  return dict;
}

注意事项

• 性能： 该算法包含嵌套循环，其时间复杂度大致为 O(N^2)，其中 N 是输入字符串列表的长度。对于非常大的数据集，这可能不是最优解。
• 子域定义： 代码中子域的提取逻辑 substring(indexOf(".") + 1) 意味着它只考虑第一个点号之后的后缀。如果需要更灵活的后缀匹配（例如，匹配任意长度的共同后缀），则需要调整 subdomain 的提取逻辑，可能需要结合Trie树或后缀树等数据结构。
• 空字符串或无点号字符串： 对于不含点号的字符串（如 "com"）或空字符串，indexOf(".") 将返回 -1，substring 行为需要注意。当前代码通过 firstDotIndex > 0 && firstDotIndex < currentString.length - 1 进行了初步的边界检查，避免了对 com 这样的顶级域进行子域提取。

示例用法

下面是使用上述 filterBySubdomain 函数处理不同输入列表的示例：

// 示例 1: 初始数据集
const x1 = [
  "samsung.phone.com",
  "lg.phone.com",
  "phone.com",
  "camera.dsrl.nikon.com",
  "amd.gpu.com",
  "intel.cpu.com",
];
const result1 = filterBySubdomain(x1);
console.log("结果 1:", result1);

// 示例 2: 添加 "cpu.com"
const x2 = [
  "samsung.phone.com",
  "lg.phone.com",
  "phone.com",
  "camera.dsrl.nikon.com",
  "amd.gpu.com",
  "intel.cpu.com",
  "cpu.com", // 新增
];
const result2 = filterBySubdomain(x2);
console.log("\n结果 2:", result2);

// 示例 3: 添加 "hello.samsung.phone.com"
const x3 = [
  "samsung.phone.com",
  "lg.phone.com",
  "phone.com",
  "camera.dsrl.nikon.com",
  "amd.gpu.com",
  "intel.cpu.com",
  "cpu.com",
  "hello.samsung.phone.com", // 新增
];
const result3 = filterBySubdomain(x3);
console.log("\n结果 3:", result3);

预期输出

结果 1: {
  'phone.com': [ 'samsung.phone.com', 'lg.phone.com' ],
  'camera.dsrl.nikon.com': [],
  'amd.gpu.com': [],
  'intel.cpu.com': []
} 

结果 2: {
  'phone.com': [ 'samsung.phone.com', 'lg.phone.com' ],
  'camera.dsrl.nikon.com': [],
  'amd.gpu.com': [],
  'cpu.com': [ 'intel.cpu.com' ]
} 

结果 3: {
  'samsung.phone.com': [ 'hello.samsung.phone.com' ],
  'phone.com': [ 'lg.phone.com' ],
  'camera.dsrl.nikon.com': [],
  'amd.gpu.com': [],
  'cpu.com': [ 'intel.cpu.com' ]
}

总结

本教程提供了一个实用的JavaScript解决方案，用于根据最长子域后缀对字符串进行分组。通过分步的字典初始化、子域关系识别和精炼过滤，该方法能够准确地实现所需的层次化分组逻辑。虽然其性能在处理海量数据时可能存在局限，但对于中小型数据集，它提供了一个清晰且可维护的实现方案。在实际应用中，开发者应根据具体的数据规模和性能要求，权衡是否需要采用更复杂但效率更高的算法。

今天关于《JavaScript最长子域后缀分组技巧》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！