1410. HTML 實體解析器

1410. HTML 實體解析器

代碼倉庫地址： https://github.com/slience-me/Leetcode

個人博客 ：https://slienceme.xyz

• 編寫一個函數來查找字符串數組中的最長公共前綴。

  如果不存在公共前綴，返回空字符串 ""。

• 「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 字符中的任意字符。

方案1：暴力解

第一種純暴力解，遍歷替換

class Solution {
public:string entityParser(string text) {unordered_map<string, string> myMap = {{"&quot;",  "\""},{"&apos;",  "\'"},{"&amp;",   "&"},{"&gt;",    ">"},{"&lt;",    "<"},{"&frasl;", "/"}};for (const auto &map: myMap){string searchString = map.first;string replacementString = map.second;size_t pos = text.find(searchString); // 找到第一個匹配的位置// 循環替換所有匹配的內容while (pos != string::npos) {text.replace(pos, searchString.length(), replacementString); // 用替換字符串替換匹配字符串pos = text.find(searchString, pos + replacementString.length()); // 繼續找下一個匹配的位置}}return text;}
};

執行用時分布 744ms 擊敗11.76%使用 C++ 的用戶

消耗內存分布16.37MB 擊敗90.20%使用 C++ 的用戶

方案2

發現沒有優化太多，反而超時了

class Solution {
public:string entityParser(string text) {unordered_map<string, string> myMap = {{"&quot;",  "\""},{"&apos;",  "\'"},{"&amp;",   "&"},{"&gt;",    ">"},{"&lt;",    "<"},{"&frasl;", "/"}};for (int i = 0; i < text.length(); ++i){string temp="&";if (text[i]=='&'){if (text[i+1]=='\0' || text[i+1]=='&'){continue;}int indexj = i+1;while (text[indexj]!=';'){if (indexj>=text.length()){break;}temp += text[indexj];indexj+=1;}if (indexj>=text.length()){break;}temp += ';';size_t index = replaceStr(text, myMap, temp);if (index != -1){i = index;}} else if(text[i]=='\0'){continue;}}return text;}size_t replaceStr(string &text, unordered_map<string, string> &myMap, const string &temp) const {if(myMap.find(temp) != myMap.end()){string searchString = myMap.find(temp)->first;string replacementString = myMap.find(temp)->second;size_t pos = text.find(searchString); // 找到第一個匹配的位置// 循環替換所有匹配的內容text.replace(pos, searchString.length(), replacementString); // 用替換字符串替換匹配字符串return pos+replacementString.length()-1;}return -1;}
};

超出時間限制

測試用例通過了，但耗時太長。

方案3

最后的優化

class Solution {
public:string entityParser(string text) {string result = "";int i = 0;int n = text.length();while (i < n) {if (text[i] == '&') {if (text.substr(i, 6) == "&quot;") {result += "\"";i += 6;} else if (text.substr(i, 6) == "&apos;") {result += "'";i += 6;} else if (text.substr(i, 5) == "&amp;") {result += "&";i += 5;} else if (text.substr(i, 4) == "&gt;") {result += ">";i += 4;} else if (text.substr(i, 4) == "&lt;") {result += "<";i += 4;} else if (text.substr(i, 7) == "&frasl;") {result += "/";i += 7;} else {result += text[i];i++;}} else {result += text[i];i++;}}return result;}
};

執行用時分布 68ms 擊敗80.39%使用 C++ 的用戶

消耗內存分布 18.54MB 擊敗35.29%使用 C++ 的用戶