LC.P1410[HTML实体解析器]

方法一：模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    private static final Map<String, String> map = new HashMap<>(){{
        put("&quot;", "\"");
        put("&apos;", "'");
        put("&amp;", "&");
        put("&gt;", ">");
        put("&lt;", "<");
        put("&frasl;", "/");
    }};

    public String entityParser(String text) {
        StringBuilder builder = new StringBuilder();
        int n = text.length();
        for (int i = 0; i < n; ++i) {
            char c = text.charAt(i);
            if (c == '&') {
                int j = i + 1;
                boolean flag = false;
                for (; j < n && text.charAt(j) != ';'; ++j) {
                    if (text.charAt(j) == '&') {
                        builder.append(text, i, j);
                        i = j - 1;
                        flag = true;
                        break;
                    }
                }
                if (flag) continue;
                String s = text.substring(i, j == n ? n : j + 1);
                i = j;
                s = map.getOrDefault(s, s);
                builder.append(s);
            } else {
                builder.append(c);
            }
        }
        return builder.toString();
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(C)$，$C$ 为固定的特殊字符哈希表大小

方法二：模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {

    private static final Map<String, String> map = new HashMap<>() {{
        put("&quot;", "\"");
        put("&apos;", "'");
        put("&amp;", "&");
        put("&gt;", ">");
        put("&lt;", "<");
        put("&frasl;", "/");
    }};

    public String entityParser(String text) {
        int n = text.length();
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < n; ) {
            if (text.charAt(i) == '&') {
                int j = i + 1;
                while (j < n && j - i < 6 && text.charAt(j) != ';') ++j;
                String s = text.substring(i, Math.min(j + 1, n));
                if (map.containsKey(s)) {
                    builder.append(map.get(s));
                    i = j + 1;
                    continue;
                }
            }
            builder.append(text.charAt(i++));
        }
        return builder.toString();
    }
}
  • 时间复杂度：$O(nk)$，其中 $k = 6$ 为最大特殊字符长度
  • 空间复杂度：$O(C)$