【LetMeFly】1410.HTML 實體解析器：字符串匹配
力扣題目鏈接：https://leetcode.cn/problems/html-entity-parser/
「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 字符中的任意字符。
方法一：字符串匹配
一共就6種要替換的情況，我們可以先把6種要替換的情況都存下來到一個數組中（理解為哈希表也可以）。
接著就開始愉快地遍歷text字符串了：
- 如果當前字符為
&：- 遍歷替換數組，如果能匹配則將答案字符串加上要替換的結果
- 如果全部匹配不上就加上當前字符
- 否則：答案字符串加上當前字符
最終返回答案字符串即可。
- 時間復雜度 O ( l e n ( t e x t ) × k ) O(len(text)\times k) O(len(text)×k)，其中 k k k是要替換字符串的評價長度
- 空間復雜度 O ( C ) O(C) O(C)，只有“替換數組”占據了常數大小的空間
AC代碼
C++
const static vector<pair<string, char>> dic = {{""", '"'},{"'", '\''},{"&", '&'},{">", '>'},{"<", '<'},{"⁄", '/'}
};class Solution {
public:string entityParser(string& text) {string ans;for (int i = 0; i < text.size(); i++) {if (text[i] == '&') {for (auto&& [from, to] : dic) {if (text.substr(i, from.size()) == from) {ans += to;i += from.size() - 1;goto loop;}}}ans += text[i];loop:;}return ans;}
};
Python
dic = [('"', '"'),(''', "'"),('>', '>'),('<', '<'),('⁄', '/'),('&', '&')
]class Solution:def entityParser(self, text: str) -> str:ans = ''i = 0while i < len(text):matched = Falseif text[i] == '&':for from_, to in dic:if text[i: len(from_) + i] == from_:matched = Trueans += toi += len(from_)breakif not matched:ans += text[i]i += 1return ans
同步發文于CSDN，原創不易，轉載經作者同意后請附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/134571778
