Python, Straightforward with Explanation

  • 1

    Let's check for the valid closed tag first. The function collect_tag(i) will find the tag that starts at S[i] == '<' and ends at S[j] == '>' and output S[i+1:j].

    Afterwards, S will be just the content section between the valid closed tag. Whenever a tag could start, we complete it, overriding our usual checks if it is part of some cdata. Otherwise, an opening tag goes on the stack, and a closing tag is checked against the top of the stack.

    def isValid(self, S):
        CDATA_BEGIN = '![CDATA['
        CDATA_END = ']]>'
        def collect_tag(i):
            for j in xrange(i, len(S)):
                if S[j] == '>': break
                return None
            return S[i+1:j]
        def valid_tag(tag):
            return 1 <= len(tag) <= 9 and all('A' <= c <= 'Z' for c in tag)
        if not S or S[0] != '<': return False
        tag = collect_tag(0)
        if (tag is None or 
                not S.startswith('<{}>'.format(tag)) or 
                not S.endswith('</{}>'.format(tag)) or
                not valid_tag(tag)):
            return False
        S = S[len(tag) + 2: -len(tag) - 3]
        i = 0
        stack = []
        while i < len(S):
            if S[i] == '<':
                tag = collect_tag(i)
                if tag is None: return False
                if tag.startswith(CDATA_BEGIN):
                    while i < len(S) and S[i:i+3] != CDATA_END:
                        i += 1
                    if not S[i:i+3] == CDATA_END:
                        return False
                    i += 2
                elif tag.startswith('/'):
                    tag = tag[1:]
                    if not valid_tag(tag) or not stack or stack.pop() != tag:
                        return False
                    if not valid_tag(tag):
                        return False
            i += 1
        return not stack

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.