题目描述

HTML 实体解析器 是一种特殊的解析器，它将 HTML 代码作为输入，并用字符本身替换掉所有这些特殊的字符实体。

HTML 里这些特殊字符和它们对应的字符实体包括：

• 双引号：字符实体为 "，对应的字符是 "。
• 单引号：字符实体为 '，对应的字符是 '。
• 与符号：字符实体为 &，对应对的字符是 &。
• 大于号：字符实体为 >，对应的字符是 >。
• 小于号：字符实体为 <，对应的字符是 <。
• 斜线号：字符实体为 ⁄，对应的字符是 /。

给你输入字符串 text，请你实现一个 HTML 实体解析器，返回解析器解析后的结果。

样例

输入：text = "& is an HTML entity but &ambassador; is not."
输出："& is an HTML entity but &ambassador; is not."
解释：解析器把字符实体 & 用 & 替换

输入：text = "and I quote: "...""
输出："and I quote: \"...\""

输入：text = "Stay home! Practice on Leetcode :)"
输出："Stay home! Practice on Leetcode :)"

输入：text = "x > y && x < y is always false"
输出："x > y && x < y is always false"

输入：text = "leetcode.com⁄problemset⁄all"
输出："leetcode.com/problemset/all"

限制

• 1 <= text.length <= 10^5
• 字符串可能包含 256 个 ASCII 字符中的任意字符。

算法

(线性扫描) $O(n)$

1. 扫描数组，在遇到 '&' 时，判断后边若干个字符是否符合要求。

时间复杂度

• 最坏情况下，每个字符需要判断六种情况，判断的时间复杂度为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 可以直接在原地构造新的字符串，仅需要常数的额外空间。

C++ 代码

class Solution {
private:
    bool check(const string &s, int idx, const string &p) {
        if (s.size() - idx < p.size())
            return false;

        for (int i = 0; i < p.size(); i++, idx++)
            if (s[idx] != p[i])
                return false;

        return true;
    }

public:
    string entityParser(string text) {
        const int n = text.size();
        int j = 0;

        for (int i = 0; i < n; i++) {
            if (text[i] != '&') {
                text[j++] = text[i];
                continue;
            }

            if (check(text, i + 1, "quot;")) {
                text[j++] = '"';
                i += 5;
            } else if (check(text, i + 1, "apos;")) {
                text[j++] = '\'';
                i += 5;
            } else if (check(text, i + 1, "amp;")) {
                text[j++] = '&';
                i += 4;
            } else if (check(text, i + 1, "gt;")) {
                text[j++] = '>';
                i += 3;
            } else if (check(text, i + 1, "lt;")) {
                text[j++] = '<';
                i += 3;
            } else if (check(text, i + 1, "frasl;")) {
                text[j++] = '/';
                i += 6;
            } else {
                text[j++] = '&';
            }
        }

        text.resize(j);
        return text;
    }    
};