Package g0501_0600.s0591_tag_validator

Class Solution

java.lang.Object
g0501_0600.s0591_tag_validator.Solution
public class Solution extends Object
591 - Tag Validator.<p>Hard</p> <p>Given a string representing a code snippet, implement a tag validator to parse the code and return whether it is valid.</p> <p>A code snippet is valid if all the following rules hold:</p> <ol> <li>The code must be wrapped in a <strong>valid closed tag</strong>. Otherwise, the code is invalid.</li> <li>A <strong>closed tag</strong> (not necessarily valid) has exactly the following format : <code><TAG_NAME>TAG_CONTENT</TAG_NAME></code>. Among them, <code><TAG_NAME></code> is the start tag, and <code></TAG_NAME></code> is the end tag. The TAG_NAME in start and end tags should be the same. A closed tag is <strong>valid</strong> if and only if the TAG_NAME and TAG_CONTENT are valid.</li> <li>A <strong>valid</strong> <code>TAG_NAME</code> only contain <strong>upper-case letters</strong> , and has length in range [1,9]. Otherwise, the <code>TAG_NAME</code> is <strong>invalid</strong>.</li> <li>A <strong>valid</strong> <code>TAG_CONTENT</code> may contain other <strong>valid closed tags</strong> , <strong>cdata</strong> and any characters (see note1) <strong>EXCEPT</strong> unmatched <code><</code>, unmatched start and end tag, and unmatched or closed tags with invalid TAG_NAME. Otherwise, the <code>TAG_CONTENT</code> is <strong>invalid</strong>.</li> <li>A start tag is unmatched if no end tag exists with the same TAG_NAME, and vice versa. However, you also need to consider the issue of unbalanced when tags are nested.</li> <li>A <code><</code> is unmatched if you cannot find a subsequent <code>></code>. And when you find a <code><</code> or <code></</code>, all the subsequent characters until the next <code>></code> should be parsed as TAG_NAME (not necessarily valid).</li> <li>The cdata has the following format : <code><![CDATA[CDATA_CONTENT]]></code>. The range of <code>CDATA_CONTENT</code> is defined as the characters between <code><![CDATA[</code> and the <strong>first subsequent</strong> <code>]]></code>.</li> <li><code>CDATA_CONTENT</code> may contain <strong>any characters</strong>. The function of cdata is to forbid the validator to parse <code>CDATA_CONTENT</code>, so even it has some characters that can be parsed as tag (no matter valid or invalid), you should treat it as <strong>regular characters</strong>.</li> </ol> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> code = &ldquo;<DIV>This is the first line <![CDATA[<div>]]></DIV>&rdquo;</p> <p><strong>Output:</strong> true</p> <p><strong>Explanation:</strong></p> <pre><code> The code is wrapped in a closed tag : <DIV> and </DIV>. The TAG_NAME is valid, the TAG_CONTENT consists of some characters and cdata. Although CDATA_CONTENT has an unmatched start tag with invalid TAG_NAME, it should be considered as plain text, not parsed as a tag. So TAG_CONTENT is valid, and then the code is valid. Thus return true. </code></pre> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> code = &ldquo;<DIV>>> ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>&rdquo;</p> <p><strong>Output:</strong> true</p> <p><strong>Explanation:</strong></p> <pre><code> We first separate the code into : start_tag|tag_content|end_tag. start_tag -> &quot;<DIV>&quot; end_tag -> &quot;</DIV>&quot; tag_content could also be separated into : text1|cdata|text2. text1 -> &quot;>> ![cdata[]] &quot; cdata -> &quot;<![CDATA[<div>]>]]>&quot;, where the CDATA_CONTENT is &quot;<div>]>&quot; text2 -> &quot;]]>>]&quot; The reason why start_tag is NOT &quot;<DIV>>>&quot; is because of the rule 6. The reason why cdata is NOT &quot;<![CDATA[<div>]>]]>]]>&quot; is because of the rule 7. </code></pre> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> code = &ldquo;<A> <B> </A> </B>&rdquo;</p> <p><strong>Output:</strong> false</p> <p><strong>Explanation:</strong> Unbalanced. If &ldquo;<A>&rdquo; is closed, then &ldquo;<B>&rdquo; must be unmatched, and vice versa.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= code.length <= 500</code></li> <li><code>code</code> consists of English letters, digits, <code>'<'</code>, <code>'>'</code>, <code>'/'</code>, <code>'!'</code>, <code>'['</code>, <code>']'</code>, <code>'.'</code>, and <code>' '</code>.</li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • isValid

      public boolean isValid(String code)