0591. Tag Validator

题目信息

题号:

0591

难度:

Hard

主题:

标签字符串、嵌套结构、CDATA、整体合法性

原题:

LeetCode 0591

重点:

整段代码必须由唯一根标签包围、标签名为 1 至 9 个大写字母、闭合顺序正确、CDATA 只在标签内容中有效

题目重述

给定字符串 code,判断它是否是合法的标签代码。整个字符串必须恰好由一个完整根标签包围,根标签之外不能出现任何字符。

开始标签写作 <TAG_NAME>,结束标签写作 </TAG_NAME>;标签名长度位于 [1, 9],并且只能包含大写英文字母。标签可以正确嵌套。标签内容中可以出现 <![CDATA[...]]>,其中的文本不按标签解析,直到最近的 ]]> 为止;CDATA 不能出现在任何标签之外。

自建示例

CDATA 中的标签样式文本不解析:

输入:code = "<A><![CDATA[<B>text</B>]]></A>"
输出:true
解释:整个字符串由 A 标签包围,CDATA 内的尖括号内容按普通文本处理。

存在两个根标签:

输入:code = "<A></A><B></B>"
输出:false
解释:第一个根标签闭合后仍有第二段标签,整段代码没有唯一根节点。

按栈解析唯一根标签

扫描字符串时维护当前尚未闭合的标签栈。遇到开始标签就校验标签名并入栈,遇到结束标签就要求它与栈顶完全相同后出栈;CDATA 必须位于非空栈中,并整体跳过直到 ]]>。普通文本只有在标签栈非空时才合法,根标签闭合后不允许再出现任何内容。

C++ 实现

class Solution {
    bool validName(const std::string& name) {
        if (name.empty() || name.size() > 9) return false;
        for (char c : name) {
            if (c < 'A' || c > 'Z') return false;
        }
        return true;
    }

public:
    bool isValid(std::string code) {
        std::vector<std::string> tags;
        bool seenRoot = false;
        bool rootClosed = false;
        int i = 0;

        while (i < static_cast<int>(code.size())) {
            if (code[i] != '<') {
                if (tags.empty()) return false;
                ++i;
                continue;
            }

            if (code.compare(i, 9, "<![CDATA[") == 0) {
                if (tags.empty()) return false;
                std::size_t end = code.find("]]>", i + 9);
                if (end == std::string::npos) return false;
                i = static_cast<int>(end + 3);
                continue;
            }

            if (i + 1 < static_cast<int>(code.size()) &&
                code[i + 1] == '/') {
                std::size_t end = code.find('>', i + 2);
                if (end == std::string::npos) return false;
                std::string name =
                    code.substr(i + 2, end - (i + 2));
                if (!validName(name) || tags.empty() ||
                    tags.back() != name) {
                    return false;
                }
                tags.pop_back();
                i = static_cast<int>(end + 1);
                if (tags.empty()) rootClosed = true;
                continue;
            }

            std::size_t end = code.find('>', i + 1);
            if (end == std::string::npos) return false;
            std::string name = code.substr(i + 1, end - (i + 1));
            if (!validName(name)) return false;
            if (tags.empty()) {
                if (rootClosed) return false;
                seenRoot = true;
            }
            tags.push_back(name);
            i = static_cast<int>(end + 1);
        }

        return seenRoot && rootClosed && tags.empty();
    }
};

代码分析

栈顶记录最近打开且尚未闭合的标签,因此每次闭合都同时检查嵌套顺序和标签名称;CDATA 直接定位结束标记,避免把其中的 < 误当成标签。只有第一次打开的标签可以成为根节点,根标签闭合后 rootClosed 阻止后续内容。每个字符最多被扫描和定位一次,时间复杂度为 O(n),标签栈与临时名称占用 O(n) 空间。