LeetCode Solutions

			

class Solution {
 public:
  bool isValid(string code) {
    if (code[0] != '<' || code.back() != '>')
      return false;

    stack<string> stack;

    for (int i = 0; i < code.length(); ++i) {
      int closeIndex = 0;
      if (stack.empty() && containsTag)
        return false;
      if (code[i] == '<') {
        // Inside a tag, so we can check if it's a cdata
        if (!stack.empty() && code[i + 1] == '!') {
          closeIndex = code.find("]]>", i + 2);
          if (closeIndex == string::npos ||
              !isValidCdata(code.substr(i + 2, closeIndex - i - 2)))
            return false;
        } else if (code[i + 1] == '/') {  // End tag
          closeIndex = code.find('>', i + 2);
          if (closeIndex == string::npos ||
              !isValidTagName(stack, code.substr(i + 2, closeIndex - i - 2),
                              true))
            return false;
        } else {  // Start tag
          closeIndex = code.find('>', i + 1);
          if (closeIndex == string::npos ||
              !isValidTagName(stack, code.substr(i + 1, closeIndex - i - 1),
                              false))
            return false;
        }
        i = closeIndex;
      }
    }

    return stack.empty() && containsTag;
  }

 private:
  bool containsTag = false;

  bool isValidCdata(const string& s) {
    return s.find("[CDATA[") == 0;
  }

  bool isValidTagName(stack<string>& stack, const string& tagName,
                      bool isEndTag) {
    if (tagName.empty() || tagName.length() > 9)
      return false;

    for (const char c : tagName)
      if (!isupper(c))
        return false;

    if (isEndTag) {
      if (stack.empty())
        return false;
      if (stack.top() != tagName)
        return false;
      stack.pop();
      return true;
    }

    containsTag = true;
    stack.push(tagName);
    return true;
  }
};

			

class Solution {
  public boolean isValid(String code) {
    if (code.charAt(0) != '<' || code.charAt(code.length() - 1) != '>')
      return false;

    Deque<String> stack = new ArrayDeque<>();

    for (int i = 0; i < code.length(); ++i) {
      int closeIndex = 0;
      if (stack.isEmpty() && containsTag)
        return false;
      if (code.charAt(i) == '<') {
        // Inside a tag, so we can check if it's a cdata
        if (!stack.isEmpty() && code.charAt(i + 1) == '!') {
          closeIndex = code.indexOf("]]>", i + 2);
          if (closeIndex < 0 || !isValidCdata(code.substring(i + 2, closeIndex)))
            return false;
        } else if (code.charAt(i + 1) == '/') { // End tag
          closeIndex = code.indexOf('>', i + 2);
          if (closeIndex < 0 || !isValidTagName(stack, code.substring(i + 2, closeIndex), true))
            return false;
        } else { // Start tag
          closeIndex = code.indexOf('>', i + 1);
          if (closeIndex < 0 || !isValidTagName(stack, code.substring(i + 1, closeIndex), false))
            return false;
        }
        i = closeIndex;
      }
    }

    return stack.isEmpty() && containsTag;
  }

  private boolean containsTag = false;

  private boolean isValidCdata(final String s) {
    return s.indexOf("[CDATA[") == 0;
  }

  private boolean isValidTagName(Deque<String> stack, String tagName, boolean isEndTag) {
    if (tagName.isEmpty() || tagName.length() > 9)
      return false;

    for (final char c : tagName.toCharArray())
      if (!Character.isUpperCase(c))
        return false;

    if (isEndTag)
      return !stack.isEmpty() && stack.pop().equals(tagName);

    containsTag = true;
    stack.push(tagName);
    return true;
  }
}

			

class Solution:
  def isValid(self, code: str) -> bool:
    if code[0] != '<' or code[-1] != '>':
      return False

    containsTag = False
    stack = []

    def isValidCdata(s: str) -> bool:
      return s.find('[CDATA[') == 0

    def isValidTagName(tagName: str, isEndTag: bool) -> bool:
      nonlocal containsTag
      if not tagName or len(tagName) > 9:
        return False
      if any(not c.isupper() for c in tagName):
        return False

      if isEndTag:
        return stack and stack.pop() == tagName

      containsTag = True
      stack.append(tagName)
      return True

    i = 0
    while i < len(code):
      if not stack and containsTag:
        return False
      if code[i] == '<':
        # Inside a tag, so we can check if it's a cdata
        if stack and code[i + 1] == '!':
          closeIndex = code.find(']]>', i + 2)
          if closeIndex == -1 or not isValidCdata(code[i + 2:closeIndex]):
            return False
        elif code[i + 1] == '/':  # End tag
          closeIndex = code.find('>', i + 2)
          if closeIndex == -1 or not isValidTagName(code[i + 2:closeIndex], True):
            return False
        else:  # Start tag
          closeIndex = code.find('>', i + 1)
          if closeIndex == -1 or not isValidTagName(code[i + 1:closeIndex], False):
            return False
        i = closeIndex
      i += 1

    return not stack and containsTag