射阳建设局网站,汕头响应式网站,天津市建设厅网站,义乌网站建设公司排名Every day a Leetcode
题目来源#xff1a;1410. HTML 实体解析器
解法1#xff1a;模拟
遍历字符串 text#xff0c;每次遇到 ’‘#xff0c;就判断以下情况#xff1a;
双引号#xff1a;字符实体为 quot; #xff0c;对应的字符是 。单引号1410. HTML 实体解析器
解法1模拟
遍历字符串 text每次遇到 ’‘就判断以下情况
双引号字符实体为 quot; 对应的字符是 。单引号字符实体为 apos; 对应的字符是 ’ 。与符号字符实体为 amp; 对应对的字符是 。大于号字符实体为 gt; 对应的字符是 。小于号字符实体为 lt; 对应的字符是 。斜线号字符实体为 frasl; 对应的字符是 / 。
如果是上述情况将转换结果插入结果如果都不是则直接添加到结果里。
代码
/** lc appleetcode.cn id1410 langcpp** [1410] HTML 实体解析器*/// lc codestart
class Solution
{
public:string entityParser(string text){string result;int i 0;while (i text.size()){if (text[i] ){if (text.substr(i, 4) gt;){result ;i 4;}else if (text.substr(i, 4) lt;){result ;i 4;}else if (text.substr(i, 5) amp;){result ;i 5;}else if (text.substr(i, 6) quot;){result ;i 6;}else if (text.substr(i, 6) apos;){result \;i 6;}else if (text.substr(i, 7) frasl;){result /;i 7;}elseresult text[i];}elseresult text[i];}return result;}
};
// lc codeend结果 复杂度分析
时间复杂度O(n)其中 n 是字符串 text 的长度。
空间复杂度O(1)。
解法2模拟
本题要求把字符串中所有的「字符实体」替换成对应的字符。
「字符实体」都是由 开头的所以我们只需要遍历一遍字符串用一个变量 pos\textit{pos}pos 表示当前处理的位置如果 text[pos]‘’就在这个位置进行探测。假设一个「字符实体」为 e对应的字符为 c那么可以通过判断 pos 位置开始长度和 e 相同的子串是否和 e 相等如果相等就可以替换。
代码
class Solution {
public:using EntityChar pair string, char;vector EntityChar entityList;string entityParser(string text) {entityList vector({(EntityChar){quot;, },(EntityChar){apos;, \},(EntityChar){amp;, },(EntityChar){gt;, },(EntityChar){lt;, },(EntityChar){frasl;, /}});string r ;for (int pos 0; pos text.size(); ) {bool isEntity false;if (text[pos] ) {for (const auto [e, c]: entityList) {if (text.substr(pos, e.size()) e) {r.push_back(c);pos e.size();isEntity true;break;}}}if (!isEntity) {r.push_back(text[pos]);continue;}}return r;}
};结果 复杂度分析
时间复杂度O(k×n)其中 n 是字符串 text 的长度。考虑最坏情况每个位置都是 那么每个位置都要进行 6 次探测探测的总时间代价和「实体字符」的总长度 k 相关这里 k66544732。
空间复杂度O(k)这里用了 entityList 作为辅助变量字符总数为 k6故渐进空间复杂度为 O(k6)O(k)。
