Every day a Leetcode

題目來源：1410. HTML 實體解析器

解法1：模擬

遍歷字符串 text，每次遇到 ’&‘，就判斷以下情況：

• 雙引號：字符實體為 " ，對應(yīng)的字符是 " 。
• 單引號：字符實體為 ' ，對應(yīng)的字符是 ’ 。
• 與符號：字符實體為 & ，對應(yīng)對的字符是 & 。
• 大于號：字符實體為 > ，對應(yīng)的字符是 > 。
• 小于號：字符實體為 &lt; ，對應(yīng)的字符是 < 。
• 斜線號：字符實體為 &frasl; ，對應(yīng)的字符是 / 。

如果是上述情況，將轉(zhuǎn)換結(jié)果插入結(jié)果；如果都不是，則直接添加到結(jié)果里。

代碼：

/** @lc app=leetcode.cn id=1410 lang=cpp** [1410] HTML 實體解析器*/// @lc code=start
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 code=end

結(jié)果：

復(fù)雜度分析：

時間復(fù)雜度：O(n)，其中 n 是字符串 text 的長度。

空間復(fù)雜度：O(1)。

解法2：模擬

本題要求把字符串中所有的「字符實體」替換成對應(yīng)的字符。

「字符實體」都是由 & 開頭的，所以我們只需要遍歷一遍字符串，用一個變量 pos\textit{pos}pos 表示當前處理的位置，如果 text[pos]=‘&’，就在這個位置進行探測。假設(shè)一個「字符實體」為 e，對應(yīng)的字符為 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;}
};

結(jié)果：

復(fù)雜度分析：

時間復(fù)雜度：O(k×n)，其中 n 是字符串 text 的長度?？紤]最壞情況，每個位置都是 &，那么每個位置都要進行 6 次探測，探測的總時間代價和「實體字符」的總長度 k 相關(guān)，這里 k=6+6+5+4+4+7=32。

空間復(fù)雜度：O(k)，這里用了 entityList 作為輔助變量，字符總數(shù)為 k+6，故漸進空間復(fù)雜度為 O(k+6)=O(k)。