力扣00022.括号生成

发表于 分类于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 6 分钟
括号生成、字符串、动态规划、回溯、中等

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

示例 2：

输入：n = 1
输出：[“()”]

提示：

  • 1 <= n <= 8

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<std::string> generateParenthesis(int n) {
        vector<string> result;
        generate("", n, n, result);
        return result;
    }
private:
    void generate(string current, int left, int right, vector<string>& result) {
        if (left == 0 && right == 0) {
            result.push_back(current);
            return;
        }
        if (left > 0) {
            generate(current + '(', left - 1, right, result);
        }
        if (right > left) {
            generate(current + ')', left, right - 1, result);
        }
    }
};

结果

执行用时 : 4 ms, 击败 70.78% 使用 C++ 的用户

内存消耗 : 15.12 MB, 击败 31.77% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generate("", n, n, result);
        return result;
    }
    private void generate(String current, int left, int right, List<String> result) {
        if (left == 0 && right == 0) {
            result.add(current);
            return;
        }
        if (left > 0) {
            generate(current + '(', left - 1, right, result);
        }
        if (right > left) {
            generate(current + ')', left, right - 1, result);
        }
    }
}

结果

执行用时 : 1 ms, 击败 71.45% 使用 Java 的用户

内存消耗 : 42.19 MB, 击败 31.97% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        def generate(current, left, right, result):
            if left == 0 and right == 0:
                result.append(current)
                return
            if left > 0:
                generate(current + '(', left - 1, right, result)
            if right > left:
                generate(current + ')', left, right - 1, result)
        result = []
        generate("", n, n, result)
        return result

结果

执行用时 : 20 ms, 击败 61.89% 使用 Python 的用户

内存消耗 : 13.23 MB, 击败 66.19% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(current, left, right, result):
            if left == 0 and right == 0:
                result.append(current)
                return
            if left > 0:
                generate(current + '(', left - 1, right, result)
            if right > left:
                generate(current + ')', left, right - 1, result)
        result = []
        generate("", n, n, result)
        return result

结果

执行用时 : 24 ms, 击败 99.93% 使用 Python3 的用户

内存消耗 : 17.18 MB, 击败 13.63% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void backTarck(int n, int *returnSize, char **returnStr, int leftNum, int rightNum, char *stack, int top) {
    if ((rightNum + leftNum) >= 2 * n) { 
        // 当前长度已达2n
        stack[top] = '\0';
        returnStr[*returnSize] = (char*)malloc(sizeof(char) * (top + 1));
        strcpy(returnStr[*returnSize], stack);
        (*returnSize)++;
        return;
    }
    if (leftNum < n) {
        stack[top] = '(';
        backTarck(n, returnSize, returnStr, leftNum + 1, rightNum, stack, top + 1);
    }
    if (rightNum < leftNum) {
        stack[top] = ')';
        backTarck(n, returnSize, returnStr, leftNum, rightNum + 1, stack, top + 1);
    }
}
char** generateParenthesis(int n, int *returnSize) {
    char **returnStr = (char **)malloc(sizeof(char *) * 2000);
    char *stack = (char *)malloc(sizeof(char) * (n * 2 + 1));
    *returnSize = 0;
    backTarck(n, returnSize, returnStr, 0, 0, stack, 0);
    return returnStr;
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 C 的用户

内存消耗 : 7.05 MB, 击败 72.42% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public IList<string> GenerateParenthesis(int n) {
        IList<string> result = new List<string>();
        Generate(result, "", 0, 0, n);
        return result;
    }
    private void Generate(IList<string> result, string current, int left, int right, int n) {
        if (current.Length == 2 * n) {
            result.Add(current);
            return;
        }
        if (left < n) {
            Generate(result, current + '(', left + 1, right, n);
        }
        if (right < left) {
            Generate(result, current + ')', left, right + 1, n);
        }
    }
}

结果

执行用时 : 84 ms, 击败 98.27% 使用 C# 的用户

内存消耗 : 48.10 MB, 击败 12.14% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let result = [];
    function generate(current, left, right) {
        if (current.length === 2 * n) {
            result.push(current);
            return;
        }
        if (left < n) {
            generate(current + '(', left + 1, right);
        }
        if (right < left) {
            generate(current + ')', left, right + 1);
        }
    }
    generate('', 0, 0);
    return result;
};

结果

执行用时 : 68 ms, 击败 33.89% 使用 JavaScript 的用户

内存消耗 : 49.30 MB, 击败 9.30% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function generateParenthesis(n: number): string[] {
    const result: string[] = [];
    function generate(current: string, left: number, right: number): void {
        if (current.length === 2 * n) {
            result.push(current);
            return;
        }
        if (left < n) {
            generate(current + '(', left + 1, right);
        }
        if (right < left) {
            generate(current + ')', left, right + 1);
        }
    }
    generate('', 0, 0);
    return result;
}

结果

执行用时 : 84 ms, 击败 13.04% 使用 TypeScript 的用户

内存消耗 : 50.48 MB, 击败 9.88% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    /**
     * @param Integer $n
     * @return String[]
     */
    function generateParenthesis($n) {
        $result = [];
        $this->backtrack('', 0, 0, $n, $result);
        return $result;
    }
    function backtrack($current, $left, $right, $n, &$result) {
        if (strlen($current) === 2 * $n) {
            array_push($result, $current);
            return;
        }
        if ($left < $n) {
            $this->backtrack($current . '(', $left + 1, $right, $n, $result);
        }
        if ($right < $left) {
            $this->backtrack($current . ')', $left, $right + 1, $n, $result);
        }
    }
}

结果

执行用时 : 12 ms, 击败 25.00% 使用 PHP 的用户

内存消耗 : 19.68 MB, 击败 18.75% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    func generateParenthesis(_ n: Int) -> [String] {
        var result: [String] = []
        backtrack("", 0, 0, n, &result)
        return result
    }
    func backtrack(_ current: String, _ left: Int, _ right: Int, _ n: Int, _ result: inout [String]) {
        if current.count == 2 * n {
            result.append(current)
            return
        }
        if left < n {
            backtrack(current + "(", left + 1, right, n, &result)
        }
        if right < left {
            backtrack(current + ")", left, right + 1, n, &result)
        }
    }
}

结果

执行用时 : 24 ms, 击败 8.82% 使用 Swift 的用户

内存消耗 : 15.61 MB, 击败 7.84% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val result: MutableList<String> = mutableListOf()
        backtrack("", 0, 0, n, result)
        return result
    }
    private fun backtrack(current: String, left: Int, right: Int, n: Int, result: MutableList<String>) {
        if (current.length == 2 * n) {
            result.add(current)
            return
        }
        if (left < n) {
            backtrack("$current(", left + 1, right, n, result)
        }
        if (right < left) {
            backtrack("$current)", left, right + 1, n, result)
        }
    }
}

结果

执行用时 : 204 ms, 击败 15.38% 使用 Kotlin 的用户

内存消耗 : 36.29 MB, 击败 75.38% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
  List<String> generateParenthesis(int n) {
    List<String> result = [];
    _backtrack('', 0, 0, n, result);
    return result;
  }
  void _backtrack(String current, int left, int right, int n, List<String> result) {
    if (current.length == 2 * n) {
      result.add(current);
      return;
    }
    if (left < n) {
      _backtrack('$current(', left + 1, right, n, result);
    }
    if (right < left) {
      _backtrack('$current)', left, right + 1, n, result);
    }
  }
}

结果

执行用时 : 288 ms, 击败 50.00% 使用 Dart 的用户

内存消耗 : 147.64 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func generateParenthesis(n int) []string {
	var result []string
	backtrack("", 0, 0, n, &result)
	return result
}
func backtrack(current string, left int, right int, n int, result *[]string) {
	if len(current) == 2*n {
		*result = append(*result, current)
		return
	}
	if left < n {
		backtrack(current+"(", left+1, right, n, result)
	}
	if right < left {
		backtrack(current+")", left, right+1, n, result)
	}
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Go 的用户

内存消耗 : 2.61 MB, 击败 62.59% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# @param {Integer} n
# @return {String[]}
def generate_parenthesis(n)
  result = []
  backtrack('', 0, 0, n, result)
  result
end
def backtrack(current, left, right, n, result)
  if current.length == 2 * n
    result << current
    return
  end
  if left < n
    backtrack(current + '(', left + 1, right, n, result)
  end
  if right < left
    backtrack(current + ')', left, right + 1, n, result)
  end
end

结果

执行用时 : 48 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.92 MB, 击败 12.50% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
object Solution {
  def generateParenthesis(n: Int): List[String] = {
    var result: List[String] = List()
    def backtrack(current: String, left: Int, right: Int): Unit = {
      if (current.length == 2 * n) {
        result = current :: result
        return
      }
      if (left < n) {
        backtrack(current + "(", left + 1, right)
      }
      if (right < left) {
        backtrack(current + ")", left, right + 1)
      }
    }
    backtrack("", 0, 0)
    result
  }
}

结果

执行用时 : 452 ms, 击败 -% 使用 Scala 的用户

内存消耗 : 52.77 MB, 击败 100.00% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
impl Solution {
    pub fn generate_parenthesis(n: i32) -> Vec<String> {
        let mut result = Vec::new();
        Self::backtrack(String::new(), 0, 0, n, &mut result);
        result
    }
    fn backtrack(current: String, left: i32, right: i32, n: i32, result: &mut Vec<String>) {
        if current.len() as i32 == 2 * n {
            result.push(current);
            return;
        }
        if left < n {
            let mut new_current = current.clone();
            new_current.push('(');
            Self::backtrack(new_current, left + 1, right, n, result);
        }
        if right < left {
            let mut new_current = current.clone();
            new_current.push(')');
            Self::backtrack(new_current, left, right + 1, n, result);
        }
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.31 MB, 击败 18.09% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户