LC 1410. HTML 实体解析器

题目描述

这是 LeetCode 上的 1410. HTML 实体解析器 ，难度为 中等。

「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 字符中的任意字符。

---

模拟

每个特殊字符均以 & 开头，最长一个特殊字符为 ⁄。

从前往后处理 text，若遇到 & 则往后读取最多 $6$ 个字符（中途遇到结束字符 ; 则终止），若读取子串为特殊字符，将使用替换字符进行拼接，否则使用原字符进行拼接。

Java 代码：

class Solution {
    public String entityParser(String text) {
        Map<String, String> map = new HashMap<>(){{
            put("&quot;", "\"");
            put("&apos;", "'");
            put("&amp;", "&");
            put("&gt;", ">");
            put("&lt;", "<");
            put("&frasl;", "/");
        }};
        int n = text.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ) {
            if (text.charAt(i) == '&') {
                int j = i + 1;
                while (j < n && j - i < 6 && text.charAt(j) != ';') j++;
                String sub = text.substring(i, Math.min(j + 1, n));
                if (map.containsKey(sub)) {
                    sb.append(map.get(sub));
                    i = j + 1;
                    continue;
                }
            }
            sb.append(text.charAt(i++));
        }
        return sb.toString();
    }
}

C++ 代码：

class Solution {
public:
    string entityParser(string text) {
        unordered_map<string, string> entityMap = {
            {"&quot;", "\""},
            {"&apos;", "'"},
            {"&amp;", "&"},
            {"&gt;", ">"},
            {"&lt;", "<"},
            {"&frasl;", "/"}
        };
        int n = text.length();
        string ans = "";
        for (int i = 0; i < n; ) {
            if (text[i] == '&') {
                int j = i + 1;
                while (j < n && j - i < 6 && text[j] != ';') j++;
                string sub = text.substr(i, min(j + 1, n) - i);
                if (entityMap.find(sub) != entityMap.end()) {
                    ans += entityMap[sub];
                    i = j + 1;
                    continue;
                }
            }
            ans += text[i++];
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def entityParser(self, text: str) -> str:
        entity_map = {
            """: "\"",
            "'": "'",
            "&": "&",
            ">": ">",
            "&lt;": "<",
            "&frasl;": "/"
        }
        i, n = 0, len(text)
        ans = ""
        while i < n:
            if text[i] == '&':
                j = i + 1
                while j < n and j - i < 6 and text[j] != ';':
                    j += 1
                sub = text[i:min(j + 1, n)]
                if sub in entity_map:
                    ans += entity_map[sub]
                    i = j + 1
                    continue
            ans += text[i]
            i += 1
        return ans

TypeScript 代码：

function entityParser(text: string): string {
    const entityMap: { [key: string]: string } = {
        """: "\"",
        "'": "'",
        "&": "&",
        ">": ">",
        "&lt;": "<",
        "&frasl;": "/"
    };
    const n = text.length;
    let ans = "";
    for (let i = 0; i < n; ) {
        if (text[i] == '&') {
            let j = i + 1;
            while (j < n && j - i < 6 && text[j] != ';') j++;
            const sub = text.substring(i, Math.min(j + 1, n));
            if (entityMap[sub]) {
                ans += entityMap[sub];
                i = j + 1;
                continue;
            }
        }
        ans += text[i++];
    }
    return ans;
};

• 时间复杂度：$O(n \times K)$，其中 $K = 6$ 为最大特殊字符长度
• 空间复杂度：$O(C)$，一个固定大小的哈希表

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1410 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。