Question

1410. HTML Entity Parser

中文文档

Description

HTML entity parser is the parser that takes HTML code as input and replace all the entities of the special characters by the characters itself.

The special characters and their entities for HTML are:

• Quotation Mark: the entity is " and symbol character is ".
• Single Quote Mark: the entity is ' and symbol character is '.
• Ampersand: the entity is & and symbol character is &.
• Greater Than Sign: the entity is > and symbol character is >.
• Less Than Sign: the entity is < and symbol character is <.
• Slash: the entity is ⁄ and symbol character is /.

Given the input text string to the HTML parser, you have to implement the entity parser.

Return _the text after replacing the entities by the special characters_.

 

Example 1:

Input: text = "& is an HTML entity but &ambassador; is not."
Output: "& is an HTML entity but &ambassador; is not."
Explanation: The parser will replace the & entity by &

Example 2:

Input: text = "and I quote: "...""
Output: "and I quote: \"...\""

 

Constraints:

• 1 <= text.length <= 105
• The string may contain any possible characters out of all the 256 ASCII characters.

Solutions

Solution 1: Hash Table + Simulation

We can use a hash table to store the corresponding character for each character entity. Then, we traverse the string, and when we encounter a character entity, we replace it with the corresponding character.

The time complexity is $O(n \times l)$, and the space complexity is $O(l)$. Here, $n$ is the length of the string, and $l$ is the total length of the character entities.

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;
}

Solution 2

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]);
}