Ruby on Rails中按关联规则合并嵌套数组并生成指定字符串

问题描述 #

给定嵌套数组 [["GJ","MP"],["HR","MH"],["MP","KL"],["KL","HR"]]，需按以下规则生成结果字符串 "GJ, MP, KL, HR, MH"：

• 以第一个子数组 ["GJ","MP"] 生成初始序列 ["GJ", "MP"]
• 每次用上一个序列的最后元素，匹配下一个子数组的首元素，找到后将该子数组的尾元素追加到序列中
• 重复上述步骤直到无法找到匹配的子数组

实现思路 #

1. 构建映射表：将每个子数组的首元素作为键、尾元素作为值，把原始数组转换成键值对结构，实现快速查找后续元素
2. 初始化序列：直接取第一个子数组的所有元素作为初始序列
3. 链式追加元素：循环取当前序列的最后一个元素，去映射表中查找对应的尾元素，找到就追加到序列，直到找不到匹配项为止
4. 转换为目标字符串：将最终序列用 , 连接成字符串

代码实现（JavaScript） #

const arr = [["GJ","MP"],["HR","MH"],["MP","KL"],["KL","HR"]];

// 构建映射表
const map = new Map();
arr.forEach(item => map.set(item[0], item[1]));

// 初始化序列
const result = [...arr[0]];

// 链式追加元素
let last = result[result.length - 1];
while (map.has(last)) {
  const next = map.get(last);
  result.push(next);
  last = next;
}

// 转换为字符串
const finalStr = result.join(', ');
console.log(finalStr); // 输出: "GJ, MP, KL, HR, MH"

说明 #

• 映射表让查找操作的时间复杂度降到O(1)，整体执行效率更高
• 循环终止条件为当前最后一个元素不在映射表的键中，说明无后续匹配子数组，停止追加
• 该方法适用于任意长度的链式结构，只要原始子数组能形成完整的链

内容的提问来源于stack exchange，提问作者Pooja M