我在某个地方遇到过这个问题，这很有趣。
问题:
Write a string formatting function that turns the data object into a formatted VALID HTML string
const data = {
str: 'hello world',
formatting: [
{
type: 'i',
positions: [2, 4],
},
{
type: 'i',
positions: [5, 9],
},
{
type: 'b',
positions: [7, 13],
}
]
}
function outputHTMLString(data) {
}
预期输出: (注意:必须是有效的 HTML)
he<i>ll</i>o<i> w</i><b><i>or</i></b><b>ld</b>
我遇到的问题是，因为它必须是有效的 HTML，所以我需要打破 <i/>在位置 7。这非常令人困惑。在过去的 1 小时里，我一直在努力思考。任何帮助将不胜感激。
这是我的尝试:(不是很理想)
const data = {
s: 'hello world',
formatting: [{
type: 'i',
positions: [2, 4],
},
{
type: 'i',
positions: [5, 9],
},
{
type: 'b',
positions: [7, 13],
}
]
}
function outputHTMLString(data) {
const formMap = data.formatting.reduce((acc, elem, index) => {
for (let p of elem.positions) {
const e = [p, elem.type];
acc.push(e);
}
return acc;
}, []);
formMap.sort((a, b) => {
return a[0] - b[0];
});
// console.log(formMap);
const len = data.s.length;
let s = data.s.split('');
let current;
const stack = [];
let last = ''; //i0 = <i>, i1=</i>, b0=<b>, b1=</b>
for (let [i, arr] of formMap.entries()) {
// console.log(i, arr, stack);
const index = arr[0],
elem = arr[1],
topStack = stack[stack.length - 1];
if (s[index]) {
if (stack.length) {
if (topStack === elem) {
let current = s[index];
s[index] = '';
while (stack.length) {
s[index] += '</' + stack.pop() + '>';
}
const next = formMap[i + 1][0];
console.log('stack:', stack, index + 1, 'next:', next);
if (next > index) {
s[index] += '<' + formMap[i + 1][1] + '>';
}
s[index] += current;
} else {
s[index] = '</' + stack.pop() + '>' + '<' + elem + '>' + '<' + topStack + '>' + (s[index] || '');
stack.push(elem, topStack);
}
} else {
s[index] = '<' + elem + '>' + (s[index] || '');
stack.push(elem);
}
} else if (index > len - 1) {
s[len - 1] = s[len - 1] + '</' + elem + '>';
}
}
console.log(s);
}
console.log(outputHTMLString(data));最佳答案
我可以想到两种方法来解决这个问题。
使用树
定义一个树数据结构来表示正在构建的 HTML 内容。每个节点都知道它的 start和 end原始字符串中的索引。要在索引范围内进行格式化，请找到树中与该范围重叠的所有节点。
这棵树是“三元”的，因为它也代表 start和 end格式化内容的索引，每个节点可以有 left和 right这些索引左侧和右侧的内容的 child 。
使用堆栈
对于每个格式化范围，插入对 (start, '<tag>')和 (end, '</tag>')放入列表中，然后按每对的第一个组件排序。按顺序遍历对；当您看到一个开放标签时，将标签名称压入堆栈并写入开放标签。当您看到一个关闭标签时，如果它的标签名称在堆栈顶部，则将其弹出并写入结束标签。
否则，在写入结束标签时，将其他标签名称从堆栈中弹出到临时堆栈中，直到弹出要关闭的标签名称。然后关闭它，并重新打开临时堆栈中的所有标签(以相反的顺序)，同时将它们推回主堆栈。
例如，如果当前输出是he<i>ll</i>o<i> w<b>or接下来要做的是关闭 <i>标签，然后我们弹出 b从主堆栈并将其插入临时堆栈，写入 </b>到输出，弹出i从主堆栈写入 </i>到输出，然后弹出 b从临时堆栈并将其推回主堆栈，写入 <b>到输出。
下面是堆栈解决方案的快速实现:
function formatHTML(text, formats) {
const boundaries = formats.map(f => ({
tag: f.type, open: true, position: f.positions[0]
})).concat(formats.map(f => ({
tag: f.type, open: false, position: f.positions[1]
}))).sort((a, b) => a.position - b.position);
const out = [];
const stack = [];
var i = 0;
for (let boundary of boundaries) {
out.push(text.substring(i, boundary.position));
if (boundary.open) {
stack.push(boundary.tag);
out.push('<', boundary.tag, '>');
} else {
const tmp = [];
while (true) {
const t = stack.pop();
out.push('</', t, '>');
if(t == boundary.tag) { break; }
tmp.push(t);
}
while (tmp.length) {
const t = tmp.pop();
stack.push(t);
out.push('<', t, '>');
}
}
i = boundary.position;
}
out.push(text.substring(i));
return out.join('');
}
这不是最优的，因为当多个标签应该在同一位置打开或关闭时，它不会尝试以最小化总体所需标签数量的方式对它们进行排序。测试用例的输出是:
he<i>ll</i>o<i> w<b>or</b></i><b>ld</b>
关于javascript - HTML 字符串格式化函数算法问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59181316/