Question

1410. HTML 实体解析器

English Version

题目描述

「HTML 实体解析器」 是一种特殊的解析器，它将 HTML 代码作为输入，并用字符本身替换掉所有这些特殊的字符实体。

HTML 里这些特殊字符和它们对应的字符实体包括：

• 双引号：字符实体为 " ，对应的字符是 " 。
• 单引号：字符实体为 ' ，对应的字符是 ' 。
• 与符号：字符实体为 & ，对应对的字符是 & 。
• 大于号：字符实体为 > ，对应的字符是 > 。
• 小于号：字符实体为 < ，对应的字符是 < 。
• 斜线号：字符实体为 ⁄ ，对应的字符是 / 。

给你输入字符串 text ，请你实现一个 HTML 实体解析器，返回解析器解析后的结果。

 

示例 1：

输入：text = "& is an HTML entity but &ambassador; is not."
输出："& is an HTML entity but &ambassador; is not."
解释：解析器把字符实体 & 用 & 替换

示例 2：

输入：text = "and I quote: "...""
输出："and I quote: \"...\""

示例 3：

输入：text = "Stay home! Practice on Leetcode :)"
输出："Stay home! Practice on Leetcode :)"

示例 4：

输入：text = "x > y && x < y is always false"
输出："x > y && x < y is always false"

示例 5：

输入：text = "leetcode.com⁄problemset⁄all"
输出："leetcode.com/problemset/all"

 

提示：

• 1 <= text.length <= 10^5
• 字符串可能包含 256 个ASCII 字符中的任意字符。

解法

方法一：哈希表 + 模拟

我们可以使用哈希表来存储每个字符实体对应的字符，然后遍历字符串，当遇到字符实体时，我们就将其替换为对应的字符。

时间复杂度 $O(n \times l)$，空间复杂度 $O(l)$。其中 $n$ 是字符串的长度，而 $l$ 是字符实体的总长度。

class Solution:
  def entityParser(self, text: str) -> str:
    d = {
      '"': '"',
      ''': "'",
      '&': "&",
      ">": '>',
      "&lt;": '<',
      "&frasl;": '/',
    }
    i, n = 0, len(text)
    ans = []
    while i < n:
      for l in range(1, 8):
        j = i + l
        if text[i:j] in d:
          ans.append(d[text[i:j]])
          i = j
          break
      else:
        ans.append(text[i])
        i += 1
    return ''.join(ans)

class Solution {
  public String entityParser(String text) {
    Map<String, String> d = new HashMap<>();
    d.put("&quot;", "\"");
    d.put("&apos;", "'");
    d.put("&amp;", "&");
    d.put("&gt;", ">");
    d.put("&lt;", "<");
    d.put("&frasl;", "/");
    StringBuilder ans = new StringBuilder();
    int i = 0;
    int n = text.length();
    while (i < n) {
      boolean found = false;
      for (int l = 1; l < 8; ++l) {
        int j = i + l;
        if (j <= n) {
          String t = text.substring(i, j);
          if (d.containsKey(t)) {
            ans.append(d.get(t));
            i = j;
            found = true;
            break;
          }
        }
      }
      if (!found) {
        ans.append(text.charAt(i++));
      }
    }
    return ans.toString();
  }
}

class Solution {
public:
  string entityParser(string text) {
    unordered_map<string, string> d = {
      {"&quot;", "\""},
      {"&apos;", "'"},
      {"&amp;", "&"},
      {"&gt;", ">"},
      {"&lt;", "<"},
      {"&frasl;", "/"},
    };
    string ans = "";
    int i = 0, n = text.size();
    while (i < n) {
      bool found = false;
      for (int l = 1; l < 8; ++l) {
        int j = i + l;
        if (j <= n) {
          string t = text.substr(i, l);
          if (d.count(t)) {
            ans += d[t];
            i = j;
            found = true;
            break;
          }
        }
      }
      if (!found) ans += text[i++];
    }
    return ans;
  }
};

func entityParser(text string) string {
  d := map[string]string{
    """:  "\"",
    "'":  "'",
    "&":   "&",
    ">":  ">",
    "&lt;":  "<",
    "&frasl;": "/",
  }
  var ans strings.Builder
  i, n := 0, len(text)

  for i < n {
    found := false
    for l := 1; l < 8; l++ {
      j := i + l
      if j <= n {
        t := text[i:j]
        if val, ok := d[t]; ok {
          ans.WriteString(val)
          i = j
          found = true
          break
        }
      }
    }
    if !found {
      ans.WriteByte(text[i])
      i++
    }
  }

  return ans.String()
}

function entityParser(text: string): string {
  const d: Record<string, string> = {
    '&quot;': '"',
    '&apos;': "'",
    '&amp;': '&',
    '&gt;': '>',
    '&lt;': '<',
    '&frasl;': '/',
  };

  let ans: string = '';
  let i: number = 0;
  const n: number = text.length;

  while (i < n) {
    let found: boolean = false;
    for (let l: number = 1; l < 8; ++l) {
      const j: number = i + l;
      if (j <= n) {
        const t: string = text.substring(i, j);
        if (d.hasOwnProperty(t)) {
          ans += d[t];
          i = j;
          found = true;
          break;
        }
      }
    }

    if (!found) {
      ans += text[i++];
    }
  }

  return ans;
}

方法二

function entityParser(text: string): string {
  const d: { [key: string]: string } = {
    '"': '"',
    ''': "'",
    '&': '&',
    '>': '>',
    '&lt;': '<',
    '&frasl;': '/',
  };

  const pattern = new RegExp(Object.keys(d).join('|'), 'g');
  return text.replace(pattern, match => d[match]);
}