题目描述
「HTML 实体解析器」 是一种特殊的解析器，它将 HTML 代码作为输入，并用字符本身替换掉所有这些特殊的字符实体。
HTML 里这些特殊字符和它们对应的字符实体包括：
- 双引号：字符实体为
" ，对应的字符是 " 。
- 单引号：字符实体为
' ，对应的字符是 ' 。
- 与符号：字符实体为
& ，对应对的字符是 & 。
- 大于号：字符实体为
> ，对应的字符是 > 。
- 小于号：字符实体为
< ，对应的字符是 < 。
- 斜线号：字符实体为
⁄ ，对应的字符是 / 。
给你输入字符串 text ，请你实现一个 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: \"...\""
示例 3：
输入：text = "Stay home! Practice on Leetcode :)"
输出："Stay home! Practice on Leetcode :)"
示例 4：
输入：text = "x > y && x < y is always false"
输出："x > y && x < y is always false"
示例 5：
输入：text = "leetcode.com⁄problemset⁄all"
输出："leetcode.com/problemset/all"
提示：
1 <= text.length <= 10^5- 字符串可能包含 256 个ASCII 字符中的任意字符。
解法
方法一：哈希表 + 模拟
我们可以使用哈希表来存储每个字符实体对应的字符，然后遍历字符串，当遇到字符实体时，我们就将其替换为对应的字符。
时间复杂度 $O(n \times l)$，空间复杂度 $O(l)$。其中 $n$ 是字符串的长度，而 $l$ 是字符实体的总长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution:
def entityParser(self, text: str) -> str:
d = {
'"': '"',
''': "'",
'&': "&",
">": '>',
"<": '<',
"⁄": '/',
}
i, n = 0, len(text)
ans = []
while i < n:
for l in range(1, 8):
j = i + l
if text[i:j] in d:
ans.append(d[text[i:j]])
i = j
break
else:
ans.append(text[i])
i += 1
return ''.join(ans)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | class Solution {
public String entityParser(String text) {
Map<String, String> d = new HashMap<>();
d.put(""", "\"");
d.put("'", "'");
d.put("&", "&");
d.put(">", ">");
d.put("<", "<");
d.put("⁄", "/");
StringBuilder ans = new StringBuilder();
int i = 0;
int n = text.length();
while (i < n) {
boolean found = false;
for (int l = 1; l < 8; ++l) {
int j = i + l;
if (j <= n) {
String t = text.substring(i, j);
if (d.containsKey(t)) {
ans.append(d.get(t));
i = j;
found = true;
break;
}
}
}
if (!found) {
ans.append(text.charAt(i++));
}
}
return ans.toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | class Solution {
public:
string entityParser(string text) {
unordered_map<string, string> d = {
{""", "\""},
{"'", "'"},
{"&", "&"},
{">", ">"},
{"<", "<"},
{"⁄", "/"},
};
string ans = "";
int i = 0, n = text.size();
while (i < n) {
bool found = false;
for (int l = 1; l < 8; ++l) {
int j = i + l;
if (j <= n) {
string t = text.substr(i, l);
if (d.count(t)) {
ans += d[t];
i = j;
found = true;
break;
}
}
}
if (!found) ans += text[i++];
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | func entityParser(text string) string {
d := map[string]string{
""": "\"",
"'": "'",
"&": "&",
">": ">",
"<": "<",
"⁄": "/",
}
var ans strings.Builder
i, n := 0, len(text)
for i < n {
found := false
for l := 1; l < 8; l++ {
j := i + l
if j <= n {
t := text[i:j]
if val, ok := d[t]; ok {
ans.WriteString(val)
i = j
found = true
break
}
}
}
if !found {
ans.WriteByte(text[i])
i++
}
}
return ans.String()
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | function entityParser(text: string): string {
const d: Record<string, string> = {
'"': '"',
''': "'",
'&': '&',
'>': '>',
'<': '<',
'⁄': '/',
};
let ans: string = '';
let i: number = 0;
const n: number = text.length;
while (i < n) {
let found: boolean = false;
for (let l: number = 1; l < 8; ++l) {
const j: number = i + l;
if (j <= n) {
const t: string = text.substring(i, j);
if (d.hasOwnProperty(t)) {
ans += d[t];
i = j;
found = true;
break;
}
}
}
if (!found) {
ans += text[i++];
}
}
return ans;
}
|
方法二