本教程旨在解决如何根据字符串的最长公共后缀子串（特别是域名/子域名结构）对一组字符串进行高效分组的问题。我们将通过一个JavaScript函数示例，详细解析其实现逻辑，包括如何识别子域名关系、构建分组字典，并确保每个字符串被精确地归类到其最长的匹配后缀子串下，从而生成一个结构化、易于理解的分组结果。
1. 问题描述：按最长公共后缀子串分组字符串
在处理诸如域名列表等字符串数据时，我们经常需要根据它们的最长公共后缀子串进行分组。例如，给定一个域名列表 [“samsung.phone.com”, “lg.phone.com”, “phone.com”, “camera.dsrl.nikon.com”, “amd.gpu.com”, “intel.cpu.com”]，我们的目标是创建一个字典（或映射），其中键是作为组标识的最长公共后缀子串，值是匹配该后缀的原始字符串列表。
这里的“最长公共后缀子串”特指那些在原始列表中也作为独立项出现的、且能作为其他字符串的后缀的子串。例如：
- “samsung.phone.com” 和 “lg.phone.com” 都以 “phone.com” 结尾，且 “phone.com” 也在列表中，因此它们应归类到 “phone.com” 组。
- 如果添加 “cpu.com”，则 “intel.cpu.com” 应归类到 “cpu.com” 组。
- 如果添加 “hello.samsung.phone.com”，并且 “samsung.phone.com” 也在列表中，那么 “hello.samsung.phone.com” 应该归类到 “samsung.phone.com” 组，而不是更短的 “phone.com” 组，因为 “samsung.phone.com” 是更长的匹配后缀。
最终输出的字典结构应如下所示：
{ "phone.com": ["lg.phone.com", "samsung.phone.com"], "camera.dsrl.nikon.com": [], "amd.gpu.com": [], "intel.cpu.com": [] }
注意，如果一个字符串本身没有更长的字符串以其作为后缀，它将作为键存在，但其值列表可能为空。
2. 解决方案：基于子域名的分组算法
我们将通过一个JavaScript函数 filterBySubdomain 来实现这一分组逻辑。该函数接收一个字符串列表，并返回一个分组字典。
2.1 核心算法解析
该算法分多个步骤进行，以确保准确地识别和分组字符串：
-
初始化字典： 创建一个空字典 dict，并将输入列表 domList 中的每个字符串作为键，初始化其值为一个空数组。这一步确保所有潜在的分组键都存在。
const dict = {}; // key: subdomain, value: list of domains domList.forEach((el) => (dict[el] = [])); -
识别直接子域名关系： 通过嵌套循环遍历 domList。对于每一对不同的字符串 domList[i] 和 domList[j]，检查 domList[j] 是否以 domList[i] 作为其“子域名”部分。这里的“子域名”被定义为 domList[j] 中第一个点号 . 之后的部分。如果匹配，则将 domList[j] 添加到 dict[domList[i]] 的列表中。
for (let i = 0; i < domList.length; i++) { for (let j = 0; j < domList.length; j++) { if (i !== j) { const subdomain = domList[j].substring(domList[j].indexOf(".") + 1); if (subdomain === domList[i]) { dict[domList[i]].push(domList[j]); } } } }例如，如果 domList[j] 是 “samsung.phone.com”，domList[i] 是 “phone.com”，那么 subdomain 将是 “phone.com”，匹配成功，”samsung.phone.com” 会被添加到 dict[“phone.com”] 中。
-
识别并收集所有已分组的域名： 遍历当前 dict，将所有作为值列表中的域名收集到一个 mergedDomainList 中。这个列表包含了所有被识别为某个键的“子域名”的字符串。
let mergedDomainList = []; for (const [subdomain, domainList] of Object.entries(dict)) { mergedDomainList = [...mergedDomainList, ...domainList]; } -
移除不作为分组键的项： 遍历 mergedDomainList。如果一个字符串 x 在 dict 中作为键存在，但其值列表 dict[x] 为空（即它没有其他字符串以它为直接子域名），那么它就不应该成为一个分组键。因此，将其从 dict 中删除。这一步用于清理那些虽然存在于原始列表但实际上没有扮演“分组中心”角色的字符串。
mergedDomainList.forEach((x) => { if (dict[x] && dict[x].length === 0) delete dict[x]; });例如，如果 intel.cpu.com 没有其他字符串以它为子域名，且 cpu.com 存在并成功分组了 intel.cpu.com，那么 intel.cpu.com 就不应再作为一个空键存在。
-
精炼分组列表以确保最长后缀匹配： 这是最关键的一步，用于实现“最长公共后缀子串”的逻辑。 首先，获取当前 dict 中所有剩余的键（它们是最终的分组标识）。 然后，对于 dict 中的每一个键值对，筛选其值列表：只保留那些不是当前 dict 中任何其他键的字符串。这意味着如果 samsung.phone.com 已经是一个键，那么 hello.samsung.phone.com 应该被分组到 samsung.phone.com 下，而不是 phone.com 下。通过将 samsung.phone.com 从 phone.com 的值列表中移除，我们确保了更长的后缀匹配优先。
const toRemove = Object.keys(dict); // 最终作为分组键的列表 for (const [key, value] of Object.entries(dict)) { dict[key] = value.filter(function (el) { return !toRemove.includes(el); // 移除那些本身也是分组键的字符串 }); }
2.2 示例代码
/** * 根据最长公共后缀子串（子域名）对字符串列表进行分组。 * @param {string[]} domList 包含域名和子域名的字符串列表。 * @returns {Object.<string, string[]>} 一个字典，键为子域名，值为对应的域名列表。 */ 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) { // 提取 domList[j] 的子域名部分（第一个点号之后的部分） const firstDotIndex = domList[j].indexOf("."); if (firstDotIndex === -1) continue; // 如果没有点号，则不构成子域名关系 const subdomain = domList[j].substring(firstDotIndex + 1); if (subdomain === domList[i]) { // 如果 domList[i] 是 domList[j] 的子域名 dict[domList[i]].push(domList[j]); } } } } // 3. 收集所有已被分组的域名 let mergedDomainList = []; for (const [subdomain, domainList] of Object.entries(dict)) { mergedDomainList = [...mergedDomainList, ...domainList]; } // 4. 移除那些作为键但其值列表为空的项（即它们本身没有子域名） mergedDomainList.forEach((x) => { // 检查 x 是否存在于 dict 且其值列表为空 if (dict.hasOwnProperty(x) && dict[x].length === 0) { delete dict[x]; } }); // 5. 精炼分组列表，确保最长后缀匹配原则 // 获取当前所有有效的分组键（子域名） const finalKeys = Object.keys(dict); for (const [key, value] of Object.entries(dict)) { // 过滤掉值列表中那些本身也是最终分组键的字符串 // 这确保了例如 "hello.samsung.phone.com" 会被分组到 "samsung.phone.com" // 而不是更通用的 "phone.com" dict[key] = value.filter(function (el) { return !finalKeys.includes(el); }); } return dict; }
2.3 使用示例
// 示例输入数据 const x1 = [ "samsung.phone.com", "lg.phone.com", "phone.com", "camera.dsrl.nikon.com", "amd.gpu.com", "intel.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 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 result1 = filterBySubdomain(x1); const result2 = filterBySubdomain(x2); const result3 = filterBySubdomain(x3); // 打印结果 console.log("--- 示例 1 ---"); console.log(result1); console.log("n--- 示例 2 ---"); console.log(result2); console.log("n--- 示例 3 ---"); console.log(result3);
2.4 预期输出
--- 示例 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' ] }
3. 注意事项与总结
- 性能考量： 该算法涉及多层循环和数组操作，对于非常大的输入列表，其时间复杂度可能较高。具体来说，嵌套循环识别子域名关系是 O(N^2)，后续的数组操作也会增加开销。在处理海量数据时，可能需要考虑更优化的数据结构或算法，例如使用Trie树（前缀树）来加速后缀匹配。
- “子域名”的定义： 本教程中的“子域名”特指第一个点号之后的部分。如果你的“最长公共后缀子串”定义不同（例如，不限于点号分隔，或需要考虑更复杂的模式），则需要修改 substring(domList[j].indexOf(“.”) + 1) 这一部分逻辑。
- 空列表处理： 如果一个键最终对应的列表为空，这意味着该键本身存在于原始输入中，但没有其他字符串以其作为最长公共后缀。这符合问题要求，即即使没有匹配项，该键也应存在。
- 调试技巧： 理解此类多步骤算法的最佳方法是在关键步骤设置断点，并使用 console.log 输出中间状态，逐步观察数据的变化。
通过上述 filterBySubdomain 函数，我们能够有效地根据最长公共后缀子串对字符串进行分组，尤其适用于域名或类似结构的数据整理。该方法清晰地定义了分组规则，并通过多阶段处理确保了结果的准确性和一致性。
