LeetCode Day 10

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

/**

 * @param {string} s

 * @return {boolean}

 */

var isValid = function (s) {

    let left = ['(', '[', '{']

    let right = [')', ']', '}']

    let stack = [];

    for (let c of s) {

        let index = left.indexOf(c);

        if (index > -1) {

            stack.push(c);

        } else {

            if (stack.length === 0) return false;

            let end = stack[stack.length - 1];

            if (left.indexOf(end) !== right.indexOf(c)) return false;

            stack.pop();

        }

    }

    return stack.length === 0;

};

//console.log(isValid('([)]'));

console.log(isValid('{[]}'));

LeetCode0022

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[

  "((()))",

  "(()())",

  "(())()",

  "()(())",

  "()()()"

]

思路：

简单的递归考虑，想生成n对，势必n-1对已经生成了；
对于n-1对的情况进行处理，第n对，不外乎在n-1对所有合理数组前面加一个"()"，或者后面加一个"()"，又或者用左右括号将n-1对的情况包起来；
简单的过滤掉重复项：

/**

 * @param {number} n

 * @return {string[]}

 */

var generateParenthesis = function (n) {

    if (n === 0) return [];

    if (n === 1) {

        return ['()'];

    }

    else {

        let arr = generateParenthesis(n - 1);

        let result = [];

        result = result.concat(arr.map(x => '()' + x));

        result = result.concat(arr.map(x => x + '()'));

        result = result.concat(arr.map(x => '(' + x + ')'));

        return result.filter((element, index, arr) => arr.indexOf(element) === index);

    }

};

按示例测试了一下，没错，兴冲冲的提交一下，直接就WA了。

执行结果：

解答错误

显示详情

输入:

4

输出

["()()()()","()()(())","()(())()","()(()())","()((()))","(())()()","(()())()","((()))()","(()()())","(()(()))","((())())","((()()))","(((())))"]

预期结果

["(((())))","((()()))","((())())","((()))()","(()(()))","(()()())","(()())()","(())(())","(())()()","()((()))","()(()())","()(())()","()()(())","()()()()"]

写个小代码比较一下看看究竟缺少了什么：

function compareTwoArray(a, b) {

    let result = [];

    for (let i of b) {

        if (a.indexOf(i) === -1) {

            result.push(i);

        }

    }

    return result;

}

输出的是[ '(())(())' ]，可以看到对于大于1的数组，中心区不一定只有()，也可能是)(，因此上面这种简单的想法并不能有效。
改进一下：

/**

 * @param {number} n

 * @return {string[]}

 */

var generateParenthesis = function (n) {

    if (n === 0) return [];

    if (n === 1) {

        return ['()'];

    }

    else {

        let arr = generateParenthesis(n - 1);

        let result = [];

        for (let i = 0, lens = arr.length; i < lens; i++) {

            let str = arr[i];

            for (let j = 0, lens2 = str.length; j <= lens2; j++) {

                result.push(str.slice(0, j) + '()' + str.slice(j));

            }

        }

        return result.filter((element, index, arr) => arr.indexOf(element) === index);

    }

};

结果n=8时就超时了。
问题出在filter上了，我们改用Set自动过滤；

/**

 * @param {number} n

 * @return {string[]}

 */

var generateParenthesis = function (n) {

    if (n === 0) return [];

    if (n === 1) {

        return ['()'];

    }

    else {

        let arr = generateParenthesis(n - 1);

        let result = [];

        for (let i = 0, lens = arr.length; i < lens; i++) {

            let str = arr[i];

            for (let j = 0, lens2 = str.length; j <= lens2; j++) {

                result.push(str.slice(0, j) + '()' + str.slice(j));

            }

        }

        // return result.filter((element, index, arr) => arr.indexOf(element) === index);

        let result_set = new Set(result);

        result = [];

        for (var i of result_set) {

            result.push(i);

        }

        return result;

    }

};

也可以考虑用另外一种方法来做，假定有leftBracketCount(初始值为n)个左括号，rightBracketCount(初始值也为n)个右括号。对于最终要构造的2n个字符的括号串来说，我们可以一直先用左括号，用完都行，但是我们不能连着用两个右括号，使得rightBracketCount<leftBracketCount，因为这样子已经组合好的子串就肯定不是有效括号串了(如已经构成好的子串"())"，此时消耗了1个左括号，2个右括号)。

/**

 * @param {number} n

 * @return {string[]}

 */

var generateParenthesis = function (n) {

    if (n === 0) return [];

    else {

        let result = []

        dfs('', n, n, result);

        return result;

    }

};

function dfs(str, leftBracketCount, rightBracketCount, result) {

    if (leftBracketCount === 0 && rightBracketCount === 0) {

        result.push(str);

    }

    if (leftBracketCount > rightBracketCount) {

        return;

    }

    if (leftBracketCount > 0) {

        dfs(str + '(', leftBracketCount - 1, rightBracketCount, result);

    }

    if (rightBracketCount > 0) {

        dfs(str + ')', leftBracketCount, rightBracketCount - 1, result);

    }

}

巴特西

LeetCode Day 10

思路：

最新文章

热门文章