乐趣区

关于leetcode:力扣之删除字符串中的所有相邻重复项数组栈or字符串栈

问题形容

给出由小写字母组成的字符串 S,反复项删除操作会抉择两个相邻且雷同的字母,并删除它们。

在 S 上重复执行反复项删除操作,直到无奈持续删除。

在实现所有反复项删除操作后返回最终的字符串。答案保障惟一。

示例:

输出:"abbaca"
输入:"ca"
解释:例如,在 "abbaca" 中,咱们能够删除 "bb" 因为两字母相邻且雷同,这是此时惟一能够执行删除操作的反复项。之后咱们失去字符串 "aaca",其中又只有 "aa" 能够执行反复项删除操作,所以最初的字符串为 "ca"。

力扣原题目地址:https://leetcode.cn/problems/…

解决方案

计划一 数组栈思维

var removeDuplicates = function (s) {let stack = [] // 1. 创立一个栈数组,用于存放数据
    for (let i = 0; i < s.length; i++) { // 2. 遍历字符串执行入栈出栈操作
        // 3. 一开始栈是空的,所以不必看 if,间接看 else 的操作
        if (stack.at(-1) === s[i]) { // 5. 若栈中已有的顶部数据项(最初一项)和行将要入栈的数据统一,就阐明是反复项了
            stack.pop() // 6. 反复项的话,就删除呗(行将入栈的这一项疏忽,同时把栈顶部数据即最初一项删除)} 
        // 4. 新来的这一项,入栈(尾部追加)else {stack.push(s[i]) // 栈是非凡的数组,只会用到尾部增 push、尾部删 pop
        }
    }
    // 7. 最初栈中寄存的数据就是不相邻反复的数据
    return stack.join('') // 8. 而后把栈数组转成字符串返回进去即可
};

栈的利用挺多的,不过如果遇到 "成对" 的问题需要,能够思考应用 栈的思维 去解决。即,尾部增、尾部删。

于是乎,这道题,也能够应用 字符串进行“栈”的操作,反正都是尾部增尾部删呗

  • 字符串尾部增,思考:str = str + 'newStr'
  • 字符串尾部删,思考:str = str.slice(0,-1)

删除字符串最初一项,即为截取保留字符串第 0 项到倒数第二项。留神:slice 办法截取字符串两个参数,截取的时候不包含最初一项,所以是str = str.slice(0,-1)

于是乎,便有以下解法:

计划二 字符串栈思维

var removeDuplicates = function (s) {
    let str = '' // 和上方根本一样,只不过由数组栈换成了字符串了。故不赘述了
    for (let i = 0; i < s.length; i++) {if (str.at(-1) == s[i]) {str = str.slice(0, -1) // 尾部删
        } else {str = str + s[i] // 尾部增
        }
    }
    return str
};

总结

当遇到成对呈现的问题时候,思考应用栈的思维去操作...

因为尾部增和尾部删刚好是能够去成对操作的

退出移动版