Problem statement

https://leetcode.com/problems/tag-validator/

Solution

Problem statement is not very clear and in my opinion problem is not very interesting. The idea is to use stack, where we keep our tags. There are three options we need to check: <![CDATA[, </, <. We also need to do it in this order, so we do not have conflicts.

  1. If we have <![CDATA[, we need to go 9 to the right and find ending ]]>. If we do not find it, we return False. If we find it, we go 3 steps to the right again and continue. We need only one this check, because it can be anything inside our CDATA.
  2. If we have </, then we go two steps to the right, and find corresponding end >. If we do not find it, or it is too far (more than 9 symbols), we return False immediately. Also we check that our TAG is equal to the last element in stack, if it is not the case, we return false. Go one step to the right (note, we do not check if tag has capital letters only here, it will be checked when we have opening tag).
  3. If we have <, then we go one step to the right, and find corresponding end >. If we did not find it or it is too far, we return False. Also if name of tag have some other letters than capitals, we return False. Finally, we put tag name into stack and move one step to the right.
  4. Also we need to check condition number 1, which is not very clear and at the moment test case "<![CDATA[abc]]>" is not here, but it should be added. We need to make sure that everything starts with <TAG NAME>,

Complexity

Time complexity is O(n), where n is number of symbols in code, space complexity can also be potentially O(n).

Code

class Solution:
    def isValid(self, code):
        i, n, stack = 0, len(code), []
        flag = False
        while i < n:
            print(stack)
            if i > 0 and not stack: return False
            if code.startswith("<![CDATA[", i):
                j = i + 9
                i = code.find("]]>", j)
                if i < 0: return False
                i += 3
            elif code.startswith("</", i):
                j = i + 2
                i = code.find(">", j)
                if i < 0 or not 0 < i - j <= 9: return False
                if not stack or code[j:i] != stack.pop(): return False
                i += 1        
            elif code.startswith("<", i):
                if i == 0: flag = True
                j = i + 1
                i = code.find(">", j)
                if i < 0 or not 0 < i - j <= 9: return False
                for k in range(j, i):
                    if not code[k].isupper(): return False
                stack += [code[j:i]]
                i += 1
            else:
                i += 1
        
        if not code: return False
        return not stack and flag