本教程旨在解决如何根据字符串的最长公共后缀子串（特别是域名/子域名结构）对一组字符串进行高效分组的问题。我们将通过一个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 domainsdomList.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.} 一个字典，键为子域名，值为对应的域名列表。 */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 { // 检查 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 函数，我们能够有效地根据最长公共后缀子串对字符串进行分组，尤其适用于域名或类似结构的数据整理。该方法清晰地定义了分组规则，并通过多阶段处理确保了结果的准确性和一致性。
以上就是根据最长公共后缀子串对字符串进行分组的教程的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1518032.html
微信扫一扫 
支付宝扫一扫 
