Medium
题目描述
HTML 实体解析器是一个解析器，它接受 HTML 代码作为输入，并将所有特殊字符的实体替换为字符本身。
HTML 的特殊字符及其实体如下：
- 引号：实体是
"，符号字符是" - 单引号：实体是
'，符号字符是' - 和号：实体是
&，符号字符是& - 大于号：实体是
>，符号字符是> - 小于号：实体是
<，符号字符是< - 斜杠：实体是
⁄，符号字符是/
给定输入文本字符串给 HTML 解析器，你必须实现实体解析器。
返回用特殊字符替换实体后的文本。
示例 1：
输入：text = "& is an HTML entity but &ambassador; is not."
输出："& is an HTML entity but &ambassador; is not."
解释：解析器将把 & 实体替换为 &
示例 2：
输入：text = "and I quote: "...""
输出："and I quote: \"...\""
约束条件：
1 <= text.length <= 10^5- 字符串可能包含所有 256 个 ASCII 字符中的任何字符。
解题思路
解题思路
这道题要求我们将 HTML 实体转换为对应的字符。主要有两种解决思路：
方法一：哈希表 + 逐字符扫描
建立一个哈希表存储所有的实体映射关系，然后遍历字符串：
- 遇到
&字符时，尝试匹配后续的实体 - 找到对应的分号
;后，检查这段内容是否为有效实体 - 如果是有效实体则替换，否则保持原样
方法二：字符串替换
直接使用字符串的 replace 方法，按照特定顺序替换所有实体。需要注意的是，必须先替换 &，因为其他实体都包含 & 字符，避免重复替换。
推荐解法
推荐使用方法一（哈希表），因为它更加直观，便于理解和维护，时间复杂度也是线性的。
实现要点：
- 建立实体到字符的映射表
- 遍历字符串，遇到
&时尝试匹配实体 - 匹配成功则替换，否则保持原字符
代码实现
class Solution {
public:
string entityParser(string text) {
unordered_map<string, string> entities = {
{""", "\""},
{"'", "'"},
{"&", "&"},
{">", ">"},
{"<", "<"},
{"⁄", "/"}
};
string result;
int n = text.length();
for (int i = 0; i < n; i++) {
if (text[i] == '&') {
bool found = false;
for (auto& entity : entities) {
int len = entity.first.length();
if (i + len <= n && text.substr(i, len) == entity.first) {
result += entity.second;
i += len - 1;
found = true;
break;
}
}
if (!found) {
result += text[i];
}
} else {
result += text[i];
}
}
return result;
}
};
class Solution:
def entityParser(self, text: str) -> str:
entities = {
""": '"',
"'": "'",
"&": "&",
">": ">",
"<": "<",
"⁄": "/"
}
result = []
i = 0
n = len(text)
while i < n:
if text[i] == '&':
found = False
for entity, char in entities.items():
if text[i:i+len(entity)] == entity:
result.append(char)
i += len(entity)
found = True
break
if not found:
result.append(text[i])
i += 1
else:
result.append(text[i])
i += 1
return ''.join(result)
public class Solution {
public string EntityParser(string text) {
var entities = new Dictionary<string, string> {
{""", "\""},
{"'", "'"},
{"&", "&"},
{">", ">"},
{"<", "<"},
{"⁄", "/"}
};
var result = new StringBuilder();
int n = text.Length;
for (int i = 0; i < n; i++) {
if (text[i] == '&') {
bool found = false;
foreach (var entity in entities) {
int len = entity.Key.Length;
if (i + len <= n && text.Substring(i, len) == entity.Key) {
result.Append(entity.Value);
i += len - 1;
found = true;
break;
}
}
if (!found) {
result.Append(text[i]);
}
} else {
result.Append(text[i]);
}
}
return result.ToString();
}
}
var entityParser = function(text) {
const entities = {
""": '"',
"'": "'",
"&": "&",
">": ">",
"<": "<",
"⁄": "/"
};
let result = [];
let i = 0;
const n = text.length;
while (i < n) {
if (text[i]
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n) - 其中 n 是字符串长度，每个字符最多被访问常数次 |
| 空间复杂度 | O(1) - 除了输出空间，只使用了常数大小的哈希表 |