​LeetCode刷题实战591:标签验证器

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 标签验证器,我们先来看题面:
https://leetcode-cn.com/problems/tag-validator/
​LeetCode刷题实战591:标签验证器

​LeetCode刷题实战591:标签验证器


示例                         

​LeetCode刷题实战591:标签验证器
​LeetCode刷题实战591:标签验证器


解题


class Solution {
public:
    bool isValid(string code) {
        stack<string> stk; // 用栈维护 tag_name
        for(int i = 0;i < code.size();i ++ ){
            if(code[i] == '<'){
                int j = i + 1;
                while(j < code.size() && code[j] != '>') j ++ ; // 找到与之对应的 >
                if(code[i + 1] == '/'){
                    if(stk.empty()) return false; // 没有匹配的 左标签直接反回 false
                    if(stk.top() != code.substr(i + 2, j - (i + 2))) return false; // 有匹配的 但是两个不一样
                    stk.pop(); // 记得删除栈顶
                }else if(code.substr(i, 9) != "<![CDATA["){ // 如果不是 CDATA 那么就一定是一个起始标签
                    if(i && stk.empty()) return false; // 如果有多个 tag_name 并列 返回 false
                    for(int k = i + 1;k < j;k ++ ) if(code[k] < 'A' || code[k] > 'Z') return false; // 字母不合法
                    if(j - 1 - (i + 1) + 1 > 9 || j - 1 - (i + 1) + 1 < 1) return false; // 长度不合法
                    stk.push(code.substr(i + 1, j - (i + 1))); // 压入栈中
                }else{
                    if(code.substr(i, 9) == "<![CDATA["){
                        if(stk.empty()) return false; // 如果是没有被包含在标签里的直接返回 false
                        j = i;
                        while(j < code.size() && code.substr(j, 3) != "]]>") j ++ ;
                        if(j == code.size()) return false;
                        j += 2; // 过滤掉 CDATA 里边的所有字符
                    }
                }
                i = j;
            }else{ // tag_content
                if(stk.empty()) return false; // 没有被包含进来 直接返回 false
                int j = i;
                while(j < code.size() && code[j] != '<') j ++ ; // 过滤掉中间不包含 < 的所有字符
                if(j == code.size()) return false;
                i = j - 1;
            }
        }
        if(stk.size()) return false; // 如果栈还有东西 返回false
        return true; // 万事大吉 返回 true
    }
};

作者:Lemmon_kk
链接:https://www.acwing.com/activity/content/code/content/625320/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-580题汇总,希望对你有点帮助!
LeetCode刷题实战581:最短无序连续子数组
LeetCode刷题实战582:杀掉进程
LeetCode刷题实战583:两个字符串的删除操作
LeetCode刷题实战584:寻找用户推荐人
LeetCode刷题实战585:2016年的投资
LeetCode刷题实战586:订单最多的客户
LeetCode刷题实战587:安装栅栏
LeetCode刷题实战588:设计内存文件系统
LeetCode刷题实战589:N 叉树的前序遍历
LeetCode刷题实战590:N 叉树的后序遍历

​LeetCode刷题实战591:标签验证器

本篇文章来源于微信公众号:程序IT圈

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/22522.html

发表评论

登录后才能评论

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息