1021. 删除最外层的括号

leetCode-1021. 删除最外层的括号

方法一：计数器分解原语，删除最外层再合并

1. 定义容器存储原语子串
2. 定义左括号和有括号的计数器
3. 遍历数组，读取括号的时候分别计数
4. 是否打到原语结尾，left == right
5. 遍历容器删除最外层括号

/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function(s) {
    let arr = []
    // 左右括号计数器
    let left = 0;
    let right = 0;
    // 起始原语索引
    let index = 0;
    let len = s.length;
    // 遍历字符串
    for(let i = 0; i < len; i++) {
        // 遇到左括号左索引计数
        if(s[i] === '(') {
            left++
        // 遇到右括号右索引计数
        } else if (s[i] === ')') {
            right++
        }
        // 两者相等说明原语结束
        if (left === right) {
            // 切割之后存到数组中，slice截取左开又闭 [a,b)
            arr.push(s.slice(index,i+1));
            // 初始化数据
            index = i+1;
            left = 0;
            right = 0;
        }
    }
    // 数组遍历把外层括号删除
    arr = arr.map(item => item.slice(1, -1))
    return arr.join('')
};

解法二：用字符串直接承接，截取不需要的外层括号

/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function(s) {
    // 直接用字符串承接
    let str = ''
    let left = 0
    let right = 0
    let index = 0
    let len = s.length
    for(let i = 0; i < len; i++) {
        if (s[i] === '(') {
            left++
        } else if(s[i] === ')') {
            right++
        }
        // 原语结束
        if (left === right) {
            // 截取的时候直接把外层括号去掉
            str+=s.slice(index+1, i)
            // 还原
            index = i+1
            left = 0
            right = 0
        }
    }
    return str
};

优化

1. 不需要两个计数器，一个自增自减就可以
2. 只需要把需要的加进去就行

/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function(s) {
    // 直接用字符串承接
    let str = ''
    // 计数器
    let count = 0
    let len = s.length
    for(let i = 0; i < len; i++) {
        // 遇到左括号判断是不是外层，不是外层就加元素
        if (s[i] === '(') {
            if (count > 0) str += s[i]
            count++
        // 遇到不是左括号先减，不是外层就加元素
        } else {
            count--
            if (count > 0) str += s[i]
        }
    }
    return str
};

解法二：利用栈

1. 用数组模拟一个栈，临时存储字符，代替计数器
2. 遍历字符串，根据情况进行入栈、出栈操作 2.1 左括号，入栈；有括号，左括号出栈
3. 判断栈是否为空，若为空，找到了一个完成的原语
4. 截取不含最外层括号的原语子串进行连接

/**
 * @param {string} S
 * @return {string}
 * 这次用栈数据结构再实现一遍
 */
var removeOuterParentheses = function(S) {
    let arr = S.split('')
    let result = ''
    let stack = []
    // 栈底索引
    let index = -1
    const len = arr.length
    for (let i = 0 ; i < len ; i++) {
        // 判断i是左括号还是右括号
        if ( arr[i] === '(') {
            // 说明是原语
            if (index > -1) {
                result += arr[i]
            }
            stack[++index] = arr[i]
        } else {
            stack[index--] = null
            // 判断是原语
            if (index > -1) {
                result += arr[i]
            }
        }
    }
    return result
};