LeetCode 591: Tag Validator Solution

Master LeetCode problem 591 (Tag Validator), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

591. Tag Validator

Hard

String Stack

Problem Explanation

Explanation

To solve this problem, we can use a stack to keep track of the opening tags encountered while parsing the code snippet. We need to follow the rules mentioned in the problem description to validate the code snippet.

Iterate through the code snippet character by character.
If we encounter a start tag, extract the tag name and push it onto the stack.
If we encounter an end tag, pop the top tag from the stack and check if it matches the end tag.
If we encounter CDATA, skip parsing until we find the closing CDATA tag.
At the end of the iteration, the stack should be empty if all tags are properly closed and matched.

Time Complexity: O(n) where n is the length of the code snippet Space Complexity: O(n) for the stack

Solution Code

class Solution {
    public boolean isValid(String code) {
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < code.length(); i++) {
            if (i > 0 && stack.isEmpty()) {
                return false; // Unbalanced tags
            }
            if (code.startsWith("<![CDATA[", i)) {
                int j = i + 9;
                i = code.indexOf("]]>", j);
                if (i < 0) {
                    return false; // Invalid CDATA
                }
                i += 2;
            } else if (code.startsWith("</", i)) {
                int j = i + 2;
                i = code.indexOf(">", j);
                if (i < 0 || i == j || i - j > 9) {
                    return false; // Invalid end tag
                }
                String tagName = code.substring(j, i++);
                if (stack.isEmpty() || !stack.pop().equals(tagName)) {
                    return false; // Unmatched end tag
                }
            } else if (code.startsWith("<", i)) {
                int j = i + 1;
                i = code.indexOf(">", j);
                if (i < 0 || i == j || i - j > 9) {
                    return false; // Invalid start tag
                }
                String tagName = code.substring(j, i++);
                for (int k = j; k < i; k++) {
                    if (tagName.charAt(k) < 'A' || tagName.charAt(k) > 'Z') {
                        return false; // Invalid tag name
                    }
                }
                stack.push(tagName);
            }
        }
        return stack.isEmpty();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 591 (Tag Validator)?

This page provides optimized solutions for LeetCode problem 591 (Tag Validator) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 591 (Tag Validator)?

The time complexity for LeetCode 591 (Tag Validator) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 591 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 591 in Java, C++, or Python.

Back to LeetCode Solutions