LeetCode 1410. HTML 实体解析器

2023-12-08 HGNULB 约 9 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 1410. HTML 实体解析器

题意分析

输入一段文本，把其中出现的六个特殊字符串替换成对应的单个字符：" 变双引号、' 变单引号、& 变和号、> 变大于号、< 变小于号、&frasl; 变斜杠。除此之外的内容原样保留。

关键是这份清单是封闭的，只有六项，没有数字实体也没有自定义实体。所以不需要真的写一个 HTML 解析器，也不需要按「以 & 开头、以 ; 结尾」这种通用模式去识别，凡是不在清单里的片段都算普通文本。

由此引出两个必须想清楚的边界。一是形如 &ambassador; 的串：它以 & 开头、以 ; 结尾，但整体不是六项中的任何一项，因此必须原样输出，一个字符都不能改。二是替换结果本身可能又长得像实体，例如 &gt; 一次替换后得到 >，题目要的就是这个字面结果，不能对它再解析一轮。

文本长度可到 $10^5$，字符集包含字母、数字、空格和各种标点，允许一趟线性扫描。空串是合法输入，直接返回空串。

解法：固定实体表扫描

核心思路

最省事的写法是对六个实体各调一次全局替换。这看起来能过，但顺序一旦不对就会出错：若先把 & 换成 &，原文 &gt; 就变成了 >，而后面那轮针对 > 的替换会继续把它变成 >，比正确答案多解析了一层。换个顺序把 & 放到最后，又会有别的组合出问题。根本原因是多趟替换让「替换产物」重新进入了后续趟次的扫描范围。

瓶颈清楚之后，修法也就明确了：只扫一趟，每个输出字符写出去之后就再也不回头看。这样替换产物天然免疫二次解析，因为扫描指针只会向右走，永远不会退到已输出的内容上。

于是把六个实体做成一张固定的表，从左到右扫描原文，维护指针 $i$。不变量是：任意时刻结果缓冲区里的内容，恰好是原文前 $i$ 个字符按题意解析后的最终结果，且这部分内容此后不再被修改。

每一步只需在 $i$ 处做一次判定：若当前字符不是 &，它绝不可能是任何实体的开头，直接输出并前进一位；若是 &，就拿表里六个实体逐个去试当前位置的前缀匹配，命中就输出对应字符并把 $i$ 整体跳过该实体的长度，六个都不中就说明这个 & 只是个普通字符，输出它并前进一位。两种分支都让 $i$ 严格增大，不变量随之推进到新的 $i$。

顺带一提，这六个实体互相之间没有前缀关系（&a 打头的两个是 ' 和 &，第二个字符之后就分岔了），所以表的排列顺序不影响结果，不需要按长度从长到短排序。

解题步骤

建一张常量表，每项是「实体串，替换后的字符」二元组。只有六项，用二维数组比哈希表更直白，遍历它的开销是常数。

指针 i 从 0 开始，结果用 StringBuilder（Go 里用字节切片）累积。用可变缓冲而不是字符串拼接，是因为后者在循环里会反复复制，把线性算法拖成平方。

循环体先判断 text.charAt(i) != '&'，成立就直接追加该字符、i++、进入下一轮。所有实体都以 & 起头，这条快速通道让绝大多数普通字符只花一次比较。

走到这里说明当前是 &。遍历表中六项，用「从位置 i 起是否以 key 开头」做判定；命中就追加替换字符、i += key.length()、置标记并跳出循环。指针整体跳过实体长度是关键，它保证被消费掉的实体不会被重新扫描。

用 matched 标记区分两种收尾：没有任何一项命中时，把这个 & 当普通字符追加，i 只前进一位。只前进一位而不是跳过整段，是因为紧随其后的字符仍可能是另一个实体的开头。

循环结束返回缓冲区内容。指针每轮至少加一，循环必然终止。

以 text = "& is an HTML entity but &ambassador; is not." 走一遍：$i = 0$ 处是 &，遍历表：" 不匹配，' 不匹配（第二字符 a 相同但第三字符 m 与 p 不同），& 匹配，于是输出 &，$i$ 跳到 5。从 $i = 5$ 起是 " is an HTML entity but "，全是非 & 字符，逐个原样追加，指针走到 28，此时缓冲区是 "& is an HTML entity but "。$i = 28$ 处又是 &，再次遍历表：& 需要位置 28 到 32 为 &，而原文这四个字符是 &amb 后跟 a，第四位就对不上；其余五项首字符之后立刻失配。六项全不中，matched 为假，于是把 & 当普通字符输出，$i$ 只加到 29。之后 ambassador; is not. 全部原样输出。最终结果是 "& is an HTML entity but &ambassador; is not."——第一个 & 被解析，第二个看似实体的片段被完整保留。

代码实现

class Solution {
    // 扫描到普通字符时直接输出。
    public String entityParser(String text) {
        String[][] table = {
                {"&quot;", "\""},
                {"&apos;", "'"},
                {"&amp;", "&"},
                {"&gt;", ">"},
                {"&lt;", "<"},
                {"&frasl;", "/"}
        };

        StringBuilder res = new StringBuilder();
        int i = 0;
        while (i < text.length()) {
            if (text.charAt(i) != '&') {
                res.append(text.charAt(i));
                i++;
                continue;
            }
            boolean matched = false;
            for (String[] pair : table) {
                String key = pair[0];
                if (text.startsWith(key, i)) {
                    res.append(pair[1]);
                    i += key.length();
                    matched = true;
                    break;
                }
            }

            if (!matched) {
                res.append(text.charAt(i));
                i++;
            }
        }

        return res.toString();
    }
}

func entityParser(text string) string {
    // 扫描到普通字符时直接输出。
    table := [][2]string{
        {"&quot;", "\""},
        {"&apos;", "'"},
        {"&amp;", "&"},
        {"&gt;", ">"},
        {"&lt;", "<"},
        {"&frasl;", "/"},
    }

    res := make([]byte, 0, len(text))
    for i := 0; i < len(text); {
        if text[i] != '&' {
            res = append(res, text[i])
            i++
            continue
        }
        matched := false
        for _, pair := range table {
            key := pair[0]
            if i+len(key) <= len(text) && text[i:i+len(key)] == key {
                res = append(res, pair[1]...)
                i += len(key)
                matched = true
                break
            }
        }

        if !matched {
            res = append(res, text[i])
            i++
        }
    }

    return string(res)
}

复杂度分析

时间复杂度：$O(n)$，指针每轮至少前进一位，最多走 $n$ 步；每步内部只做常数次（至多六项、每项长度不超过 7）前缀比较，属于常数开销。

空间复杂度：$O(n)$，结果缓冲区最长与原文等长；实体表是常量，只占 $O(1)$。

关键点总结

「替换产物不应被再次解析」是所有转义还原类题目的核心约束，一趟单向扫描是最省心的实现方式，多趟全局替换几乎必然踩坑。

用首字符做快速通道（不是 & 就直接输出）能把绝大多数字符的判定压到一次比较，是字符串扫描的常规提速手段。

匹配成功时指针跳过整段、失败时只前进一位，这两个步长必须分开处理；统一步长会漏掉紧邻的实体或者吞掉正常字符。

当候选串之间存在前缀关系时，必须按长度从长到短尝试；本题六项恰好互不为前缀，所以顺序无关，但这一点需要主动验证而不是默认成立。

面试视角：面试官常在写完后追问「如果实体表由调用方传入且可能很大怎么办」，答案是把表建成字典树，在 & 处沿树走一遍，把每次 $O( table )$ 的线性试探降成一次 $O(L)$ 的路径匹配；能顺势说出这个演进，比只写出六项硬编码更有说服力。

易错点总结

错误写法：对六个实体依次做全局替换：text = "&gt;" → 先替换 & 得到 >，随后针对 > 的那一轮又把它变成 >，输出 >，而正确答案是 >。

错误写法：把匹配规则写成「从 & 找到下一个 ; 之间的内容」并整段吞掉：text = "&ambassador;" → 中间片段不在清单里，却被整段消费掉，输出变成空串或原样丢失，正确答案是 &ambassador; 原封不动。

错误写法：匹配失败后让指针跳到分号之后，或直接 i += 2：text = "&>" → 第一个 & 未命中，若一次跨两位就吃掉了第二个 &，紧随的 > 再也匹配不上，输出 > 而不是正确的 &>。

错误写法：匹配成功后只让 i 前进一位，忘了跳过整个实体长度 → > 会先输出 >，随后 g、t、; 被当作普通字符原样追加，得到 >gt;。

错误写法：用 text.substring(i, i + key.length()) 取子串再比较，却不先判断右端是否越界：text = "&gt" 这类以残缺实体结尾的输入 → 截取越界抛异常；Go 里同样需要 i + len(key) <= len(text) 的守卫。

错误写法：在循环里用 res = res + c 拼接字符串 → 每次拼接都复制整个前缀，$10^5$ 长度的输入退化成 $O(n^2)$，直接超时。

错误写法：省掉 matched 标记，指望在 for 循环外靠比较 i 是否变化来判断 → 逻辑等价但极易写错边界；更糟的是若把「未匹配时追加 &」写进 for 循环内部，六项各不命中就会重复追加六个 &。

错误写法：把 Java 的替换字符写成 '\"' 之外的形式、或在 Go 里对 pair[1] 用 append(res, pair[1]) 而不是 append(res, pair[1]...) → 前者是转义书写问题，后者会因类型不匹配编译失败，因为替换值是字符串而非单字节。

错误写法：假设实体一定小写、顺手做大小写不敏感匹配 → 题目未要求，&GT; 应当原样保留，宽松匹配会把它错误地解析成 >。

相似题目

题目	难度	考察点
394. 字符串解码	中等	方括号可嵌套，需要用栈保存外层的重复次数与已拼前缀
1106. 解析布尔表达式	困难	运算符带括号且可任意嵌套，靠栈做递归下降求值
726. 原子的数量	困难	括号内的系数要向内层整体乘开，还需按字典序输出
8. 字符串转换整数 (atoi)	中等	分阶段消费前导空格、符号、数字，并处理溢出截断
722. 删除注释	中等	块注释可跨行，需在扫描时维护「是否处于注释内」的模式位
227. 基本计算器 II	中等	边扫描边按优先级归约，乘除立即结算、加减压栈