Tag Validator

Constraints

• 1 <= code.length <= 500
• code consists of English letters, digits, '<', '>', '/', '!', '[', ']', '.', and ' '.

Approach and Intuition

1. Understanding Valid Tags: A tag is considered valid if it opens and closes correctly with valid tag names, such as <DIV>content</DIV>. The tag name should be uppercase and of a length between 1 and 9 characters.

2. Valid Tag Content: Content within a tag can also have nested tags, which themselves need to be valid. CDATA sections represented by <![CDATA[...]]> can hold any form of textual content, allowing characters usually restricted or parsed differently by XML/HTML parsers.

3. Parsing the String: The main approach is to parse through the code string and use a stack to manage opening and closing tags. For each character, check if it starts a tag, ends a tag, or begins a CDATA section.

4. Handling CDATA: If a <![CDATA[ is encountered, the subsequent characters till the first ]]> are collected as CDATA content and treated as regular text.

5. Validation Using Stacks: Using a stack helps in managing tags, where an opening tag is pushed into the stack and expected to be closed with a corresponding closing tag. If at any point, a closing tag doesn't match the latest opening tag on the stack, or if after processing the entire string the stack isn't empty, the snippet is invalid.

In practical terms, each of the provided examples gives a perspective on how these definitions play out:

• Example 1 validates true as the tags enclose valid CDATA and content.
• Example 2 also validates true, showcasing how nested CDATA is handled and ignored as far as tag validation goes.
• Example 3 shows an invalid case due to unbalanced tag nesting, where <A> is closed before <B> has been closed, demonstrating the significance of maintaining order and hierarchy in nesting tags.

Solutions

import java.util.Stack;

public class Parser {
    Stack<String> nameStack = new Stack<>();
    boolean hasTag = false;

    public boolean checkTagName(String tagName, boolean isClosing) {
        if (isClosing) {
            if (!nameStack.isEmpty() && nameStack.peek().equals(tagName))
                nameStack.pop();
            else
                return false;
        } else {
            hasTag = true;
            nameStack.push(tagName);
        }
        return true;
    }

    public boolean validate(String htmlCode) {
        String regexPattern = "<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*";
        if (!Pattern.matches(regexPattern, htmlCode))
            return false;
        for (int i = 0; i < htmlCode.length(); i++) {
            boolean isEndingTag = false;
            if (nameStack.isEmpty() && hasTag)
                return false;
            if (htmlCode.charAt(i) == '<') {
                if (htmlCode.charAt(i + 1) == '!') {
                    i = htmlCode.indexOf("]]>", i + 1);
                    continue;
                }
                if (htmlCode.charAt(i + 1) == '/') {
                    i++;
                    isEndingTag = true;
                }
                int tagClose = htmlCode.indexOf('>', i + 1);
                if (tagClose < 0 || !checkTagName(htmlCode.substring(i + 1, tagClose), isEndingTag))
                    return false;
                i = tagClose;
            }
        }
        return nameStack.isEmpty();
    }
}