内容简介:[LeetCode]Tag Validator
题目描述:
Given a string representing a code snippet, you need to implement a tag validator to parse the code and return whether it is valid. A code snippet is valid if all the following rules hold:
- The code must be wrapped in a valid closed tag . Otherwise, the code is invalid.
-
A closed tag
(not necessarily valid) has exactly the following format :
<TAG_NAME>TAG_CONTENT</TAG_NAME>
. Among them,<TAG_NAME>
is the start tag, and</TAG_NAME>
is the end tag. The TAG_NAME in start and end tags should be the same. A closed tag is valid if and only if the TAG_NAME and TAG_CONTENT are valid. -
A valid
TAG_NAME
only contain upper-case letters , and has length in range [1,9]. Otherwise, theTAG_NAME
is invalid . -
A valid
TAG_CONTENT
may contain other valid closed tags , cdata and any characters (see note1) EXCEPT unmatched<
, unmatched start and end tag, and unmatched or closed tags with invalid TAG_NAME. Otherwise, theTAG_CONTENT
is invalid . - 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.
-
A
<
is unmatched if you cannot find a subsequent>
. And when you find a<
or</
, all the subsequent characters until the next>
should be parsed as TAG_NAME (not necessarily valid). -
The cdata has the following format :
<![CDATA[CDATA_CONTENT]]>
. The range ofCDATA_CONTENT
is defined as the characters between<![CDATA[
and the first subsequent]]>
. -
CDATA_CONTENT
may contain any characters . The function of cdata is to forbid the validator to parseCDATA_CONTENT
, so even it has some characters that can be parsed as tag (no matter valid or invalid), you should treat it as regular characters .
Valid Code Examples:
Input: "<DIV>This is the first line <![CDATA[<div>]]></DIV>" Output: True Explanation: 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 unmatched start tag with invalid TAG_NAME, it should be considered as plain text, not parsed as tag. So TAG_CONTENT is valid, and then the code is valid. Thus return true. Input: "<DIV>>> ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>" Output: True Explanation: We first separate the code into : start_tag|tag_content|end_tag. start_tag -> "<DIV>" end_tag -> "</DIV>" tag_content could also be separated into : text1|cdata|text2. text1 -> ">> ![cdata[]] " cdata -> "<![CDATA[<div>]>]]>", where the CDATA_CONTENT is "<div>]>" text2 -> "]]>>]" The reason why start_tag is NOT "<DIV>>>" is because of the rule 6. The reason why cdata is NOT "<![CDATA[<div>]>]]>]]>" is because of the rule 7.
Invalid Code Examples:
Input: "<A> <B> </A> </B>" Output: False Explanation: Unbalanced. If "<A>" is closed, then "<B>" must be unmatched, and vice versa. Input: "<DIV> div tag is not closed <DIV>" Output: False Input: "<DIV> unmatched < </DIV>" Output: False Input: "<DIV> closed tags with invalid tag name <b>123</b> </DIV>" Output: False Input: "<DIV> unmatched tags with invalid tag name </1234567890> and <CDATA[[]]> </DIV>" Output: False Input: "<DIV> unmatched start tag <B> and unmatched end tag </C> </DIV>" Output: False
Note:
-
For simplicity, you could assume the input code (including the any characters
mentioned above) only contain
letters
,digits
,'<'
,'>'
,'/'
,'!'
,'['
,']'
and' '
.
题目大意:
给定字符串判断是否为有效标签
整个字符串应为一个闭合标签
闭合标签的格式为<TAG_NAME>TAG_CONTENT</TAG_NAME>,其中<TAG_NAME>为标签头,</TAG_NAME>为标签尾,TAG_CONTENT为标签内容。
TAG_NAME只应当包含大写字母,长度1-9
TAG_CONTENT可包含其他有效的闭合标签,cdata以及其他有效字符,不可以包含失配的'<'、标签头和标签尾
标签头如果没有同名标签尾相互匹配,即为失配,反之亦然。然而,同时还需要考虑嵌套标签的匹配问题。
'<'如果没有'>'相互匹配,即视为失配。当遇到'<'或者'</'时,到下一个'>'之前的子串视为TAG_NAME(不一定有效)
cdata格式为:<![CDATA[CDATA_CONTENT]]>。CDATA_CONTENT为<![CDATA[与第一个]]>之间的部分。
CDATA_CONTENT可以包含任意字符。cdata的目的是防止校验器解析CDATA_CONTENT,因此即使其中包含的字符可以解析为标签,也还是将其视为普通字符。
解题思路:
栈(Stack)
可以参考括号匹配的解题思路。
Python代码:
class Solution(object): def isValid(self, code): """ :type code: str :rtype: bool """ tagStack = [] while code: if code.startswith('<![CDATA['): #CDATA if not tagStack: return False nextIdx = code.find(']]>') if nextIdx == -1: return False code = code[nextIdx + 3:] elif code.startswith('</'): nextIdx = code.find('>') if nextIdx == -1: return False tagName = code[2: nextIdx] if not tagStack or tagStack.pop()!= tagName: return False code = code[nextIdx + 1:] if not tagStack: return not code elif code.startswith('<'): nextIdx = code.find('>') if nextIdx == -1: return False tagName = code[1: nextIdx] if not re.match('^[A-Z]{1,9}$', tagName): return False tagStack.append(tagName) code = code[nextIdx + 1:] elif not tagStack: return False else: code = code[1:] return not tagStack
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
PHP for the World Wide Web, Second Edition (Visual QuickStart Gu
Larry Ullman / Peachpit Press / 2004-02-02 / USD 29.99
So you know HTML, even JavaScript, but the idea of learning an actual programming language like PHP terrifies you? Well, stop quaking and get going with this easy task-based guide! Aimed at beginning ......一起来看看 《PHP for the World Wide Web, Second Edition (Visual QuickStart Gu》 这本书的介绍吧!