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

题目描述

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

image-20220502234849134 image-20220502234915815 image-20220502234934192 image-20220502235036659

题目分析

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

"<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();
    }
};

结语

  我也将见你未见的世界,写你未写的诗篇!!!

Q.E.D.


  Java后端开发工程师一名,北漂一族,欢迎大家前来交流