]>"** text2 -> **"]]>>]"** The reason why start_tag is NOT **"

>>"** is because of the rule 6. The reason why cdata is NOT **"]>]]>]]>"** is because of the rule 7. **Example 3:** **Input:** code = " " **Output:** false **Explanation:** Unbalanced. If "" is closed, then "" must be unmatched, and vice versa. **Constraints:** * `1 <= code.length <= 500` * `code` consists of English letters, digits, `'<'`, `'>'`, `'/'`, `'!'`, `'['`, `']'`, `'.'`, and `' '`. # Approaches ## Regex-based Iterative Reduction This approach attempts to validate the code by repeatedly simplifying it. It uses regular expressions to find and replace valid, innermost structures like CDATA sections and leaf tags (tags with no nested tags). The process continues until no more simplifications can be made. If the code reduces to a valid state, it's considered valid. **Time:** O(D * N^2), where N is the length of the code and D is the maximum nesting depth. Each `replaceAll` operation can take O(N^2) time in the worst case (pattern matching and new string construction), and the loop can run up to D times. · **Space:** O(N), where N is the length of the code. Each call to `replaceAll` can create a new string of length proportional to N. **Pros:** Conceptually simple for basic cases, relying on the power of regex for pattern matching.; Can lead to very concise code if the language's regex engine is powerful enough. **Cons:** Very inefficient due to repeated string manipulations and pattern matching on potentially large strings. In Java, `String` is immutable, so each replacement creates a new string.; Regular expressions are not well-suited for parsing recursively nested structures. It's extremely difficult to formulate a regex that is both correct and robust for all the edge cases specified in the problem.; High risk of subtle bugs due to regex complexities, such as greediness, and correctly handling all validation rules simultaneously. ### Explanation The core idea is to iteratively reduce the code string by removing valid, self-contained parts. If the entire string can be successfully reduced, it's deemed valid. We can define regular expressions for the constructs we need to parse: CDATA sections and valid tags with simple text content. We repeatedly apply these regexes to remove these parts from the code. For this to work correctly, we must first ensure the code is wrapped in a single root tag, and then apply the reductions only to the content within that root tag. For example, in ``, the inner `` would be removed first, leaving ``. Then, `` would be removed, leaving an empty string, indicating success. ```java class Solution { public boolean isValid(String code) { // This regex-based approach is primarily for demonstration and is not fully robust. // It's inefficient and can fail on complex nested cases. String tempCode = code; String prevCode; // Repeatedly remove CDATA and innermost valid tags. do { prevCode = tempCode; // Replace CDATA sections with a placeholder 'c'. tempCode = prevCode.replaceAll("", "c"); // Replace valid leaf tags (no nested tags) with a placeholder 't'. tempCode = tempCode.replaceAll("<([A-Z]{1,9})>[^<]*", "t"); } while (tempCode.length() < prevCode.length()); // A valid code block should reduce to a single placeholder 't'. // This simplified check fails for cases like `` which would become "tt". // A more robust implementation is significantly more complex. return tempCode.equals("t"); } } ``` ### Algorithm - First, perform a preliminary check to see if the code is wrapped by a matching start and end tag. A simple way is to use a regular expression like `^<([A-Z]{1,9})>(.*)$`. - If this check fails, the code is invalid. Otherwise, extract the content between the outermost tags. - Enter a `while` loop that continues as long as the content string is being simplified in an iteration. - Inside the loop, store the length of the content string before any modifications. - Use `String.replaceAll()` to replace all occurrences of the CDATA pattern `` with a placeholder or an empty string. The `.*?` is crucial for a non-greedy match to respect the "first subsequent `]]>`" rule. - Use `String.replaceAll()` to replace all occurrences of the leaf tag pattern `<([A-Z]{1,9})>[^<]*` with a placeholder or an empty string. `[^<]*` ensures the tag content has no other nested tags. - After the replacements, if the content's length has not changed, break the loop as no more simplifications are possible. - After the loop terminates, the original code is considered valid if the content string has been reduced to an empty string. ## Single-Pass Stack-based Parser This is the standard and most efficient way to solve problems involving nested, balanced structures, like parentheses or XML/HTML tags. We iterate through the code string once, using a stack to keep track of the open tags. This allows us to enforce the proper nesting and matching rules in a single pass. **Time:** O(N), where N is the length of the `code` string. We iterate through the string once. Operations like `indexOf` and `substring` are used, but the main index `i` is always advanced past the processed segment, ensuring each character is examined a constant number of times in total. · **Space:** O(D), where D is the maximum nesting depth of the tags. In the worst-case scenario of fully nested tags (`...`), D can be proportional to N, making the space complexity O(N). This space is used by the stack. **Pros:** Highly efficient with a single-pass linear time complexity.; Correctly and robustly handles all specified rules, including deeply nested structures and edge cases.; It is the standard, idiomatic solution for this class of parsing problems, making it maintainable and easy to understand for developers familiar with stack-based algorithms. **Cons:** The implementation logic is more involved than a naive approach, requiring careful management of the parsing index `i` and handling multiple distinct cases (start tag, end tag, CDATA, text). ### Explanation We treat the problem as a parsing task. A stack is the perfect data structure to manage the hierarchy of open tags. The Last-In, First-Out (LIFO) nature of a stack naturally corresponds to the rule that the most recently opened tag must be the first one to be closed. The algorithm proceeds with a single pass over the input string. It maintains a stack of tag names. When a start tag is encountered, its name is pushed onto the stack. When an end tag is found, we check if it matches the tag name at the top of the stack. If it does, we pop the stack, signifying that the tag has been correctly closed. Special care is taken for CDATA sections, which are treated as plain text and skipped over. The overall validity is determined by whether the stack is empty at the very end of the string, ensuring all tags were properly closed. ```java import java.util.Stack; class Solution { public boolean isValid(String code) { Stack stack = new Stack<>(); int i = 0; while (i < code.length()) { if (code.charAt(i) != '<') { if (stack.isEmpty()) { return false; // Content outside of any tag } i++; continue; } if (i == code.length() - 1) return false; // Unclosed '<' at the end if (code.charAt(i + 1) == '/') { // End tag int j = code.indexOf('>', i + 2); if (j == -1) return false; // Unclosed end tag String tagName = code.substring(i + 2, j); if (stack.isEmpty() || !stack.pop().equals(tagName)) { return false; // Mismatched or unexpected end tag } i = j + 1; if (stack.isEmpty() && i < code.length()) { return false; // Content after the root tag closes } } else if (code.charAt(i + 1) == '!') { // CDATA if (stack.isEmpty() || i + 9 > code.length() || !code.substring(i, i + 9).equals("", i + 9); if (j == -1) return false; // Unclosed CDATA i = j + 3; } else { // Start tag int j = code.indexOf('>', i + 1); if (j == -1) return false; // Unclosed start tag String tagName = code.substring(i + 1, j); if (!isValidTagName(tagName)) { return false; } stack.push(tagName); i = j + 1; } } return stack.isEmpty(); } private boolean isValidTagName(String name) { if (name.length() < 1 || name.length() > 9) { return false; } for (char c : name.toCharArray()) { if (!Character.isUpperCase(c)) { return false; } } return true; } } ``` ### Algorithm - Initialize an empty `Stack` to store tag names. - Iterate through the `code` string with an index `i`. - If the current character `code.charAt(i)` is not `<`: - It's text content. This is only valid if the stack is not empty (i.e., we are inside a tag). If the stack is empty, return `false`. - If the current character is `<`: - Check if it's a CDATA section (``). If so, validate that the stack is not empty, find the closing `]]>`, and advance `i` past it. If any part fails, return `false`. - Check if it's an end tag (``). If so, extract the `TAG_NAME`. Check if the stack is empty or if the popped tag name from the stack doesn't match. If either is true, return `false`. Also, if the stack becomes empty after popping, we must be at the end of the string; otherwise, it implies multiple root tags, so return `false`. - Otherwise, it's a start tag (``). Extract and validate the `TAG_NAME` (1-9 uppercase letters). If valid, push it onto the stack. - Advance `i` past the entire tag or CDATA block. - After the loop finishes, the code is valid if and only if the stack is empty. # Solutions ### Java ```java class Solution { public boolean isValid(String code) { Deque stk = new ArrayDeque<>(); for (int i = 0; i < code.length(); ++i) { if (i > 0 && stk.isEmpty()) { return false; } if (code.startsWith("", i + 9); if (i < 0) { return false; } i += 2; } else if (code.startsWith("", j); if (i < 0) { return false; } String t = code.substring(j, i); if (!check(t) || stk.isEmpty() || !stk.pop().equals(t)) { return false; } } else if (code.startsWith("<", i)) { int j = i + 1; i = code.indexOf(">", j); if (i < 0) { return false; } String t = code.substring(j, i); if (!check(t)) { return false; } stk.push(t); } } return stk.isEmpty(); } private boolean check(String tag) { int n = tag.length(); if (n < 1 || n > 9) { return false; } for (char c : tag.toCharArray()) { if (!Character.isUpperCase(c)) { return false; } } return true; } } ``` ### CPP ```cpp class Solution { public: bool isValid(string code) { stack stk; for (int i = 0; i < code.size(); ++i) { if (i && stk.empty()) return false; if (code.substr(i, 9) == "", i + 9); if (i < 0) return false; i += 2; } else if (code.substr(i, 2) == "', j); if (i < 0) return false; string t = code.substr(j, i - j); if (!check(t) || stk.empty() || stk.top() != t) return false; stk.pop(); } else if (code.substr(i, 1) == "<") { int j = i + 1; i = code.find('>', j); if (i < 0) return false; string t = code.substr(j, i - j); if (!check(t)) return false; stk.push(t); } } return stk.empty(); } bool check(string tag) { int n = tag.size(); if (n < 1 || n > 9) return false; for (char &c : tag) if (!isupper(c)) return false; return true; } }; ``` ### Python ```python class Solution: def isValid(self, code: str) -> bool: def check(tag): return 1 <= len(tag) <= 9 and all(c . isupper() for c in tag) stk = [] i, n = 0, len(code) while i < n: if i and not stk: return False if code[i: i + 9] == '', i + 9) if i < 0: return False i += 2 elif code[i: i + 2] == '', j) if i < 0: return False t = code[j: i] if not check(t) or not stk or stk . pop() != t: return False elif code[i] == '<': j = i + 1 i = code . find('>', j) if i < 0: return False t = code[j: i] if not check(t): return False stk . append(t) i += 1 return not stk ```