将所有路径打印到树状列表数组的叶，并在路径中连接相应的值

Question

我有一个由键和值组成的数组，其中键是一个树状编号列表。这是输入数组：

inputArr =     [
["1", "I can "], 
["1.1", "speak "],
["1.1.1", "English."], 
["1.1.2", "Chinese "], 
["1.1.2.1", "well."], 
["1.2", "eat noodles."],
["1.3", "play football."],
["2", "I "],
["2.1", "drink."],
["2.2", "sleep."],
["3", "I am the man."],
["4", "Hire me."]
]

预期输出：

outputArr =    [
["1.1.1", "I can speak English."],
["1.1.2.1", "I can speak Chinese well."],
["1.2", "I can eat noodles."],
["1.3", "I can play football."],
["2.1", "I drink."],
["2.2", "I sleep."],
["3", "I am the man."],
["4", "Hire me."]
]

让我解释第一个输出：inputArray中的第一个叶是"1.1.1"。其路径为："1"->"1.1"->"1.1.1"。当路径中的值被级联："I can " + "speak " + "English."。

我已经研究了所有相关的stackoverflow问题。我对我的问题没有任何线索。

我正在考虑这样的算法：

iterating from bottom of the array:
if the key length is 1, it is a root parent item.
if the key above has length >1, it is a leaf item. Now, get path by splitting the key, and concatenate the corresponding values.

我试过编辑比特的代码。但它只是部分起作用。我使用的代码是：

function getSentences(arr) {
let outputArr = [],
s = [],
curr, next;
for (let i = 0; i < arr.length - 1; i++) {
curr = arr[i];
next = arr[i + 1];
if (curr[0].length == 1) {
s.push(curr[1]);
if (curr[0].length == next[0].length) outputArr.push([curr[0], s.join('')]);
} else if (curr[0].length < next[0].length) {
s.push(curr[1]);
} else if (curr[0].length >= next[0].length) {
outputArr.push([curr[0], s.join('') + curr[1]]);
if (curr[0].length > next[0].length) {
s.pop();
}
}
}
for (i = 0; s.length == next[0].length; i++) {
s.pop()
}
s.push(next[1])
outputArr.push([next[0], s.join('')])
return outputArr
}

var inputArr = [
["1", "I can "],
["1.1", "speak "],
["1.1.1", "English."],
["1.1.2", "Chinese "],
["1.1.2.1", "well."],
["1.2", "eat noodles."],
["1.3", "play football."],
["2", "I "],
["2.1", "drink."],
["2.2", "sleep."],
["3", "I am the man."],
["4", "Hire me."]
];
var outputArr = getSentences(inputArr);
console.log(outputArr);

你能建议任何更正或更新、任何替代代码、任何算法或关于问题的提示吗？任何帮助都将不胜感激。

Answer 1

您可以先构建一个树，然后获取连接的路径和字符串。

const
getPathes = ({ value = '', sub }) => sub
? Object
.entries(sub)
.flatMap(([k, v]) => getPathes(v).map(([p, s]) => [k + (p && '.') + p, value + (value && '') + s]))
: [['', value]],
input = [["1", "I can "], ["1.1", "speak "], ["1.1.1", "English."], ["1.1.2", "Chinese "], ["1.1.2.1", "well."], ["1.2", "eat noodles."], ["1.3", "play football."], ["2", "I "], ["2.1", "drink."], ["2.2", "sleep."], ["3", "I am the man."], ["4", "Hire me."]],
tree = input.reduce((t, [path, value]) => {
path.split('.').reduce((o, k) => (o.sub ??= {})[k] ??= {}, t).value = value;
return t;
}, {}),
result = getPathes(tree);
console.log(result);
console.log(tree);

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

Answer 2

假设数据总是正确排序，就像在示例中一样，我们可以使用堆栈在线性时间内完成这一操作。基本算法如下：

• 用一个伪项初始化堆栈
• 获取每个数据项
• 将数据项与堆栈顶部(TOS(进行比较
• 如果项目>TOS(如1.1>1(，将其推到堆栈并继续
• 否则，将堆栈上的所有内容串联输出
• 而项<=TOS，继续从堆栈中弹出项目
• 最后，输出堆栈上剩下的所有内容

Answer 3

这肯定可以改进，但它确实有效。

function getSentences(arr) {
let outputArr = [], s = [], curr, next;
for (let i=0; i < arr.length-1; i++) {
curr = arr[i];
next = arr[i+1];
if (curr[0].length == 1) {
s.push(curr[1]);
if (curr[0].length == next[0].length) outputArr.push([curr[0], s.join('')]);
}
else if (curr[0].length < next[0].length) {
s.push(curr[1]);
}
else if (curr[0].length >= next[0].length) {
outputArr.push([curr[0], s.join('') + curr[1]]);
if (curr[0].length > next[0].length) {
s.pop();
}
}
}
for (i=0; s.length == next[0].length; i++) {
s.pop()
}
s.push(next[1])
outputArr.push([next[0], s.join('')])
console.log(outputArr);
return outputArr
}

该函数假定类似于"；1.12.2"；不应该存在，并且数组的排序方式与示例中相同。如果你想让它与假设的"；1.12.2"；，用path.replace(/[^.]/g, "").length代替比较中的.length