今天的题目难度是困难级别,勇敢牛牛,不怕困难,冲!!!
题目描述
题目有点长,并且文字有点多。题目链接,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(); } };
结语
我也将见你未见的世界,写你未写的诗篇!!!
Q.E.D.