LeetCode 1410. HTML 实体解析器

约 5 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节
标签
字符串 哈希表

题目描述

✅ 1410. HTML 实体解析器

image-20260928224924161

image-20260928224924162

题意分析

从文本中识别题目指定的六种 HTML 实体，分别替换成引号、单引号、和号、大于号、小于号及斜杠。只识别完整且大小写一致的指定写法，其他内容原样保留。

替换只进行一层，依据始终是原始输入。新输出的字符即使又与后续内容看起来像一个实体，也不能重新解析；本题不要求实现通用 HTML 解析器。

解法：固定实体表扫描

核心思路

[!blue]

六种实体的开头都是 &，所以从左到右扫描原文时，普通字符可以直接追加到结果。遇到和号才逐一尝试固定表中的完整实体。

若当前位置匹配一个实体，将对应字符写入结果，并让输入下标前进整个实体长度。这样实体已经被完整消费，后续不会把它剩下的字母或分号再次输出。

若全部匹配失败，只原样输出当前和号，并前进一个字符，不能擅自跳到下一个分号。因为后面的字符仍可能开始一个真正合法的实体，当前失败不意味着整段内容都可以吞掉。

输入和结果缓冲分开：下标永远沿原文前进，已追加到结果中的内容不会成为新的输入，天然保证只替换一次。每次至少消费一个字符，扫描结束时原文全部处理完成。

实体数量只有六种，最长长度也固定，每次比较成本都是常数，无需额外解析状态或反复全局替换。

解题步骤

  1. 建立六种实体与替代字符的对应表，初始化空结果和输入下标。
  2. 当前不是和号时直接复制，输入下标加一。
  3. 当前是和号时，检查是否以表内某个完整实体开头。
  4. 命中则输出替代字符并跨过实体；未命中则仅复制当前字符。
  5. 输入扫描完后返回结果，不再扫描输出内容。

代码实现

class Solution {

    public String entityParser(String text) {
        String[][] table = {
            {""", "\""},
            {"'", "'"},
            {"&", "&"},
            {">", ">"},
            {"&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)$，输入下标只向前移动，实体数量和最大长度均为常数。
  • 空间复杂度：$O(n)$，保存构造中的结果；实体表为固定大小。

关键点总结

[!green]

  • 输入位置决定是否匹配，输出缓冲只接收结果，不参与后续识别。
  • 匹配成功消费整段，失败只消费一个字符，两种移动幅度不能混用。
  • 未指定实体、大小写不符或不完整的内容都保留原样。

易错点总结

[!yellow]

  • 反复对替换结果做全局替换，会把原本只需解码一层的文本继续解码。
  • 匹配失败就跳到分号，可能连同后面合法实体一起跳过。
  • 匹配成功只前进一位，会再次输出已被替换实体的剩余部分。
  • Go 截取候选前缀前要确认剩余长度足够，否则不完整尾部会造成越界。
  • 不能把未知实体删除，也不能擅自将大小写归一化后匹配。

相似题目

题目 难度 关联与区别
833. 字符串中的查找与替换 中等 同样按原始输入识别并替换，写出的新内容不应再次被当成待替换实体处理。
722. 删除注释 中等 同样单次扫描识别多字符标记，本题把实体映射为字符，原题跳过注释区段。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/24641617
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！