【前端也得会算法】415. 字符串相加 [ 困难 ]

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述：

「HTML 实体解析器」 是一种特殊的解析器，它将 HTML 代码作为输入，并用字符本身替换掉所有这些特殊的字符实体。

HTML 里这些特殊字符和它们对应的字符实体包括：

- 双引号：字符实体为 " ，对应的字符是 " 。
- 单引号：字符实体为 ' ，对应的字符是 ' 。
- 与符号：字符实体为 & ，对应对的字符是 & 。
- 大于号：字符实体为 > ，对应的字符是 > 。
- 小于号：字符实体为 &lt; ，对应的字符是 < 。
- 斜线号：字符实体为 &frasl; ，对应的字符是 / 。
复制代码

给你输入字符串 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&frasl;problemset&frasl;all"
输出："leetcode.com/problemset/all"

复制代码

提示：

• 1 <= text.length <= 10^5
• 字符串可能包含 256 个ASCII 字符中的任意字符。

二、题解：

方法一 暴力替换法

• 原理。使用replaceAll替换相应字符串为对应即可。
• 思路。
  • 建立对象存储替换键值和对应的值
  • 使用字符串replaceAll替换并重新赋值

代码：

var entityParser = function(text) {
    const map = {
        """: "\"",
        "'": "'",
        ">": ">",
        "&lt;": "<",
        "&frasl;": "/",
    }
    for(let key in map){
        text = text.replaceAll(key, map[key])
    }
    return text.replaceAll('&amp;', '&')
};
复制代码

问：为何`&`没有放进键值里
因为将`&`替换成`&`后可能会与剩下字符串里的值形成新的可替换字符实体，所以不行
复制代码

方法二 遍历寻找法

• 原理。遍历字符串，同时进行寻找可替换字符实体。
• 思路。
  • 建立对象存储替换键值和对应的值
  • 使用while遍历字符串
  • 从i开始查找‘;’(因为字符实体都具有分号结尾)
  • 找出i开始到‘;’结尾的字符串
  • 判断是否截取字符串是否是字符实体，是则替换改变i，否则继续

代码：

var entityParser = function(text) {
    const map = {
        """: "\"",
        "'": "'",
        "&": "&",
        ">": ">",
        "&lt;": "<",
        "&frasl;": "/",
    }
    let i =0
    let len = text.length
    let res = ''
    while (i<len){
        let endIndex = text.indexOf(';', i)+1
        let flagStr = text.substring(i, endIndex)
        if(text[i]==='&' && map[flagStr]){
            res += map[flagStr]
            i = endIndex
        } else {
            res += text[i]
            i++
        }
    }
    
    return res
};
复制代码

优化一下判断，代码如下：

var entityParser = function(text) {
    const map = {
        """: "\"",
        "'": "'",
        "&": "&",
        ">": ">",
        "&lt;": "<",
        "&frasl;": "/",
    }
    let i =0
    let len = text.length
    let res = ''
    while (i<len){
        if(text[i]==='&'){
            let endIndex = text.indexOf(';', i)+1
            let flagStr = text.substring(i, endIndex)
            if(map[flagStr]){
                res += map[flagStr]
                i = endIndex
                continue
            } 
        } 
        res += text[i]
        i++
    }
    
    return res
};
复制代码

三、总结

• 此题可以暴力替换法和遍历寻找法两种方案
• 暴力替换法主要是使用replaceAll替换相应字符串为对应即可，但是得注意有坑。
• 遍历寻找法主要是遍历字符串，同时进行indexOf+substring进行截取字符串寻找是否是替换字符实体实现。

文中如有错误，欢迎在评论区指正