1. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
解题思路：遍历字符串当符合（ { [ 这些字符串的时候就进行压栈，当不等于这些的时候就从栈顶拿一个出来和当前的值进行比较。
答：
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| fun main() {
var content = "([]){}"
if(match(content)){
println("符合完美括号")
}else{
println("不符合完美括号")
}
}
fun match(content: String): Boolean {
var stack = Stack<Char>()
for (value in content) {
if (value == '(' || value == '{' || value == '[') {
stack.push(value)
} else {
if(stack.size<=0){
return false
}
var currentValue = stack.pop()
when (currentValue) {
'(' -> {
if (value != ')') {
return false
}
}
'{' -> {
if (value != '}') {
return false
}
}
'[' -> {
if (value != ']') {
return false
}
}
else -> {
return false
}
}
}
}
return stack.size <= 0
}
|
2. 括号生成
数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
例子：
1
2
| 输入 n = 3
输出 ["((()))","(()())","()()()","()(())"]
|
.jpg)
这里可以发现。每次节点都有两种可能，要么是左括号，要么是右括号。并且还可以发现规律，当右括号的数量大于左括号的数量的时候，是不成立的的。所以咱们可以使用递归：
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
29
30
| public class Soulution{
public List<String> getResult(int n){
List<String> result = new ArrayList<String>();
backtracking(n,0,0,result,"");
return result;
}
public void backtracking(int n,int left,int right,List<String> result,String str){
if(right>left){
return;
}
if(left == n && right == n){
result.add(str)
return;
}
if(left < n){
backtracking(n,left+1,right,result,str+"(")
}
if(right < left){
backtracking(n,left,right+1,result,str+"(")
}
}
}
fun main() {
var solution = Solution()
var result = solution.genera(4)
for(value in result){
println(value)
}
}
|