Java&C++题解与拓展——leetcode591.标签验证器【么的新知识】

每日一题做题记录，参考官方和三叶的题解

目录

• 题目要求
• • 理解
• 思路：模拟
• • Java
  • C++
• 总结

题目要求

理解

• <+大写字母=起始标签，需找>使其闭合；
• <+/=结束标签，需找>使其闭合；
• <+!=cdata标签，需找]]>使其闭合，其内[cdata[后面的内容无需解析；
• <+其他则不合法，但可以单独出现>；
• 其他字符需在起始和结束组成的开放标签内。

思路：模拟

• 先匹配cdata的标签
  • 如果不被开放标签包裹（在最开始），那不行；
  • 如果找不到结尾的]]>也不ok。
• 开始找开放标签
  • 根据是开始还是结束分别讨论，开始则压入栈，结束则从栈中找匹配的tag。
  • 注意判定 c o d e code code的长度，若tag匹配上了但 c o d e code code还没处理完也不ok。
• 其他字符
  • 需被开放标签包裹

Java

class Solution {
    String cdataSta = ", cdataEnd = "]]>";
    public boolean isValid(String code) {
        Deque<String> stack = new ArrayDeque<>();
        int n = code.length(), i = 0;
        while(i < n) {
            if(i + 8 < n && code.substring(i, i + 9).equals(cdataSta)) { // cdata开始
                if(i == 0) // 不被开放标签包裹
                    return false;
                int j = i + 9;
                boolean ok = false;
                while(j < n && !ok) {
                    if(j + 2 < n && code.substring(j, j + 3).equals(cdataEnd)) { // cdata结束
                        j += 3;
                        ok = true;
                    }
                    else
                        j++;
                }
                if(!ok) // cdata未结束
                    return false;
                i = j;
            }
            else if(code.charAt(i) == '<') { // 起始或结束标签
                if(i == n - 1)
                    return false;
                boolean isEnd = code.charAt(i + 1) == '/'; // 是结束标签？
                int sta = isEnd ? i + 2 : i + 1, j = sta;
                while(j < n && code.charAt(j) != '>') {
                    if(!Character.isUpperCase(code.charAt(j)))
                        return false;
                    j++;
                }
                if(j == n)
                    return false;
                int len = j - sta;
                if(len < 1 || len > 9)
                    return false;
                String tag = code.substring(sta, j);
                i = j + 1;
                if(!isEnd) // 起始标签
                    stack.addLast(tag);
                else {
                    if(stack.isEmpty() || !stack.pollLast().equals(tag)) // 无对应起始标签
                        return false;
                    if(stack.isEmpty() && i < n)
                        return false;
                }
            }
            else { // 其他字符
                if(i == 0) // 不被开放标签包裹
                    return false;
                i++;
            }
        }
        return stack.isEmpty();
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)

C++

class Solution {
    string cdataSta = ", cdataEnd = "]]>";
public:
    bool isValid(string code) {
        stack<string> stack;
        int n = code.size(), i = 0;
        while(i < n) {
            if(i + 8 < n && code.substr(i, 9) == cdataSta) { // cdata开始
                if(i == 0) // 不被开放标签包裹
                    return false;
                int j = i + 9;
                bool ok = false;
                while(j < n && !ok) {
                    if(j + 2 < n && code.substr(j, 3) == cdataEnd) { // cdata结束
                        j += 3;
                        ok = true;
                    }
                    else
                        j++;
                }
                if(!ok) // cdata未结束
                    return false;
                i = j;
            }
            else if(code[i] == '<') { // 起始或结束标签
                if(i == n - 1)
                    return false;
                bool isEnd = code[i + 1] == '/'; // 是结束标签？
                int sta = isEnd ? i + 2 : i + 1, j = sta;
                while(j < n && code[j] != '>') {
                    if(!isupper(code[j]))
                        return false;
                    j++;
                }
                if(j == n)
                    return false;
                int len = j - sta;
                if(len < 1 || len > 9)
                    return false;
                string tag = code.substr(sta, j - sta);
                i = j + 1;
                if(!isEnd) // 起始标签
                    stack.push(tag);
                else {
                    if(stack.empty() || stack.top() != tag) // 无对应起始标签
                        return false;
                    stack.pop();
                    if(stack.empty() && i < n)
                        return false;
                }
            }
            else { // 其他字符
                if(i == 0) // 不被开放标签包裹
                    return false;
                i++;
            }
        }
        return stack.empty();
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)

总结

简单模拟的困难题，自己想的更复杂一点，用栈去匹配三种标签，后来发现一轮过后后面的就已经被包在开放标签了。

写的时候字符串少写了个[调了一个小时……要注意细节！

五一快乐，明天上课！

欢迎指正与讨论！