天水建设网站,阳西县网络问政平台,wordpress 物流,个人网站建设方案书框架栏目1410. HTML 实体解析器
1410. HTML 实体解析器
代码仓库地址#xff1a; https://github.com/slience-me/Leetcode
个人博客 #xff1a;https://slienceme.xyz 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀#xff0c;返回空字符串 …1410. HTML 实体解析器
1410. HTML 实体解析器
代码仓库地址 https://github.com/slience-me/Leetcode
个人博客 https://slienceme.xyz 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀返回空字符串 。 「HTML 实体解析器」 是一种特殊的解析器它将 HTML 代码作为输入并用字符本身替换掉所有这些特殊的字符实体。 HTML 里这些特殊字符和它们对应的字符实体包括 双引号 字符实体为 对应的字符是 。单引号 字符实体为 对应的字符是 。与符号 字符实体为 对应对的字符是 。大于号 字符实体为 对应的字符是 。小于号 字符实体为 对应的字符是 。斜线号 字符实体为 ⁄ 对应的字符是 / 。 给你输入字符串 text 请你实现一个 HTML 实体解析器返回解析器解析后的结果。 示例 1 输入text amp; is an HTML entity but ambassador; is not.
输出 is an HTML entity but ambassador; is not.
解释解析器把字符实体 amp; 用 替换示例 2 输入text and I quote: quot;...quot;
输出and I quote: \...\示例 3 输入text Stay home! Practice on Leetcode :)
输出Stay home! Practice on Leetcode :)示例 4 输入text x gt; y amp;amp; x lt; y is always false
输出x y x y is always false示例 5 输入text leetcode.comfrasl;problemsetfrasl;all
输出leetcode.com/problemset/all提示 1 text.length 10^5字符串可能包含 256 个ASCII 字符中的任意字符。
方案1暴力解 第一种纯暴力解遍历替换 class Solution {
public:string entityParser(string text) {unordered_mapstring, 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_mapstring, string myMap {{quot;, \},{apos;, \},{amp;, },{gt;, },{lt;, },{frasl;, /}};for (int i 0; i text.length(); i){string temp;if (text[i]){if (text[i1]\0 || text[i1]){continue;}int indexj i1;while (text[indexj]!;){if (indexjtext.length()){break;}temp text[indexj];indexj1;}if (indexjtext.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_mapstring, 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 posreplacementString.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 的用户
