【05-02】力扣每日一题

今天的题目难度是困难级别，勇敢牛牛，不怕困难，冲！！！

题目描述

题目有点长，并且文字有点多。题目链接，591. 标签验证器，题目截图如下。

题目分析

这道题目很长，其难度也在于此。不过我个人觉得，面试的时候出这种题可能性不大，笔试倒有可能出。题目太长了，懒得分析，写几个特殊的测试用例吧，从测试用例的角度来解释：

"<A></A><B></B>"

这种肯定是输出的false，因为原则1，代码必须被合法的闭合标签包围，意思也就是说需要有一个根标签包裹住，这样就可以"<ROOT><A></A><B></B></ROOT>"

"<![CDATA[wahaha]]]><![CDATA[]> wahaha]]>"
这样的也不行，因为没有根标签，全是注释标签

还有需要注意的是，对于注释标签，cdata 有如下格式：<![CDATA[CDATA_CONTENT]]>。CDATA_CONTENT 的范围被定义成 <![CDATA[ 和后续的第一个 ]]>之间的字符。所以是需要注意，第一个 ]]>与前面的<![CDATA[组成注释

其它的就没什么了，按照规则来就行

代码实现

c++实现

class Solution {
private:
    // 维护一个栈
    stack<string> stack;
public:
    bool isValid(string code) {
        // 获取字符串长度
        int n = code.length();
        int i = 0;
        if(code[0]!='<'){
            return false;
        }

        if(code[1]<'A' || code[1]>'Z'){
            return false;
        }
        while(i<n){
            if(code[i]=='<'){
                int j = i+1;
                // 判断j的合法性
                if(j>=n){
                    return false;
                }
                // 考虑cdata
                if(code[j]=='!'){
                    // 走CDATA的判断流程
                    if(j+6>=n){
                        return false;
                    }
                    string begin = code.substr(j,7);
                    if(begin!="![CDATA"){
                        return false;
                    }
                    j+=7;
                    if(code[j]=='['){
                        int k = j+1;
                        if(k>=n){
                            return false;
                        }
                        // 找到第一个]]>
                        while(k+2<n){
                            if(code[k]==']' && code[k+1]==']' && code[k+2]=='>'){
                                break;
                            }
                            k++;
                        }
                        if(k+2>=n){
                            return false;
                        }
                        j = k+1;
                    }else{
                        return false;
                    }
                }else if(code[j]=='/'){
                    // 结束标签
                    while(j<n && code[j]!='>'){
                        j++;
                    }
                    if(j>=n){
                        return false;
                    }
                    int len = j-i+1;
                    string tag = code.substr(i,len);
                    if(stack.empty()){
                        return false;
                    }else{
                        string begin_tag = stack.top();
                        stack.pop();
                        string begin_tag_name = begin_tag.substr(1,begin_tag.length()-2);
                        string end_tag_name = tag.substr(2,tag.length()-3);
                        if(begin_tag_name!=end_tag_name){
                            return false;
                        }
                    }
                    if(j!=n-1 && stack.empty()){
                        return false;
                    }
                }else{
                    // 走TAG_CONTENT的判断流程
                    while(j<n && code[j]!='>'){
                        if(code[j]<'A' || code[j]>'Z'){
                            // TAG_NAME 必须是大写字母 参考原则3
                            return false;
                        }
                        j++;
                    }
                    if(j>=n){
                        return false;
                    }
                    int len = j-i+1;
                    if(len-2<1 || len-2>9){
                        // TAG_NAME 长度在[1,9]之间 参考原则3
                        return false;
                    }
                    string tag = code.substr(i,len);
                    // 压栈
                    stack.push(tag);
                }
                i = j;
            }else{
                i++;
            }
        }
        return stack.empty();
    }
};