加入文本并优化格式

Question

我有带有格式信息（例如

text1

）的文本对象（

text2

、

[bold, italic]

等）。现在我想连接这些文本并以 HTML 格式设置它们的格式。

对于一个简单的情况，它将改变以下

text1[bold,italic]
text2[]
text3[bold]

进入此 HTML：

<b><i>text1</i></b>
text2
<b>text3</b>

但我想在可能的情况下加入格式，而不是单独格式化每个文本。比如下面这个

text1[bold,italic]
text2[bold]
text3[]

应生成以下 HTML：

<b>
  <i>text1</i>
  text2
</b>
text3

此外，我想将“最长”格式包装到 DOM 的“外部”。例如，在以下情况下，

italics

是较长的格式链，因此环绕

bold

元素：

text1[bold,italic]
text2[italic]
text3[]

结果：

<i>
  <b>text1</b>
  text2
</i>
text3

解决这个问题的好的算法方法是什么？伪代码或任何编程语言的答案都会有帮助。

Answer 1

为了最小化您必须编写的标签总数，简单的贪心算法是最佳的。 文中每个位置：

1. 如果任何格式被关闭，请写出与前面的开始标签匹配的结束标签，直到所有必需的格式被关闭；然后
2. 为需要打开的任何格式编写开始标记，按照其覆盖的文本长度的降序排列。