1
class Solution {
2
  // for the ease to check CDATA starting tag
3
  private static final char[] CDATA_TAG = {'[', 'C', 'D', 'A', 'T', 'A', '['};
4

5
  public boolean isValid(String code) {
6
    // make sure it is possible to have a start tag and an end tag
7
    if (!code.startsWith("<") || !code.endsWith(">")) {
8
      return false;
9
    }
10
    Deque<String> stack = new ArrayDeque<>();
11
    for (int i = 0; i < code.length(); ++i) {
12
      char ch = code.charAt(i);
13
      // if it is a special tag
14
      if (ch == '<') {
15
        if (i == code.length() - 1) {
16
          return false;
17
        }
18
        ch = code.charAt(++i);
19
        // is end tag
20
        if (ch == '/') {
21
          // we should have a start tag to match the end tag
22
          if (stack.isEmpty()) {
23
            return false;
24
          }
25
          // get the end tag
26
          StringBuilder sb = new StringBuilder();
27
          // build tag and move i to the > for the next round
28
          i = buildTag(code, i + 1, sb);
29
          // if tag is unmatch, return false
30
          if (!stack.pop().equals(sb.toString())) {
31
            return false;
32
          }
33
          // if no start tag left and we are not at the end. The rest content is not enclosed. ->
34
          // false
35
          if (stack.isEmpty() && i < code.length() - 1) {
36
            return false;
37
          }
38
        } else if (ch == '!') { // is CDATA tag
39
          // check if CDATA is encoded in a tag
40
          if (stack.isEmpty()) {
41
            return false;
42
          }
43
          // check CDATA and move i to the end of ]]> for the next round
44
          i = validAndMoveCDATA(code, i + 1);
45
          // the above function return -1 if CDATA is not valid
46
          if (i < 0) {
47
            return false;
48
          }
49
        } else { // start tag
50
          // TAG_NAME should not empty
51
          if (ch == '>') {
52
            return false;
53
          }
54
          StringBuilder sb = new StringBuilder();
55
          i = buildTag(code, i, sb);
56
          // TAG_NAME should less than 9
57
          if (sb.isEmpty() || sb.length() > 9) {
58
            return false;
59
          }
60
          stack.push(sb.toString());
61
        }
62
      }
63
    }
64
    return stack.isEmpty();
65
  }
66

67
  private int buildTag(String code, int start, StringBuilder sb) {
68
    int i = start;
69
    // we only go to 10 because the max length is 9
70
    for (; i < start + 10 && i < code.length(); ++i) {
71
      char ch = code.charAt(i);
72
      // find the end;
73
      if (ch == '>') {
74
        break;
75
      }
76
      // TAG_NAME should be in uppercase only
77
      if (!Character.isUpperCase(ch)) {
78
        // clear the string builder for invalid TAG_NAME
79
        sb.setLength(0);
80
        break;
81
      }
82
      sb.append(ch);
83
    }
84
    return i;
85
  }
86

87
  private int validAndMoveCDATA(String code, int start) {
88
    // the length of [CDATA[]]> is 10 we need at least 10 characters left
89
    if (code.length() - start < 10) {
90
      return -1;
91
    }
92
    // check the start part
93
    int i = start;
94
    for (int j = 0; j < CDATA_TAG.length; ++j) {
95
      char ch = code.charAt(i++);
96
      if (ch != CDATA_TAG[j]) {
97
        return -1;
98
      }
99
    }
100
    // keep the last two characters for identifying the end
101
    char prev0 = '\0';
102
    char prev1 = '\0';
103

104
    for (; i < code.length(); ++i) {
105
      char ch = code.charAt(i);
106
      if (ch == '>' && prev1 == ']' && prev0 == ']') {
107
        return i;
108
      }
109
      prev0 = prev1;
110
      prev1 = ch;
111
    }
112
    // no end found
113
    return -1;
114
  }
115
}