给定一个由 ‘[‘ ，’]’，'(‘，‘)’ 组成的字符串，请问最少插入多少个括号就能使这个字符串的所有括号左右配对。 例如当前串是 "([[])"，那么插入一个’]’即可满足。 数据范围：字符串长度满足
区块链毕设网qklbishe.com为您提供问题的解答
给定一个由 ‘[‘ ，’]’，'(‘，‘)’ 组成的字符串，请问最少插入多少个括号就能使这个字符串的所有括号左右配对。
例如当前串是 "([[])"，那么插入一个’]’即可满足。
数据范围：字符串长度满足 ![给定一个由 '[' ，']'，'('，‘)’ 组成的字符串，请问最少插入多少个括号就能使这个字符串的所有括号左右配对。 例如当前串是 "([[])"，那么插入一个']'即可满足。 数据范围：字符串长度满足](https://www.nowcoder.com/equation?tex=1%20%5Cle%20n%20%5Cle%20100%20%5C)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String s = sc.next();
int len = s.length();
int[][] dp = new int[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = 1;
}
int min;
for (int i = 1; i < len; i++) { // i 区间长度
for (int j = 0; j < len – i; j++) {
if (match(s.charAt(j), s.charAt(j + i))) {
min = dp[j + 1][j + i – 1];
} else {
min = Integer.MAX_VALUE;
}
for (int k = j; k < j + i; k++) {
min = Math.min(min, dp[j][k] + dp[k + 1][j + i]);
}
dp[j][j + i] = min;
}
}
System.out.println(dp[0][len – 1]);
}
private static boolean match(char left, char right) {
return left == ‘(‘ && right == ‘)’
|| left == ‘[‘ && right == ‘]’;
}
}
48:47
以上就是关于问题给定一个由 ‘[‘ ，’]’，'(‘，‘)’ 组成的字符串，请问最少插入多少个括号就能使这个字符串的所有括号左右配对。 例如当前串是 "([[])"，那么插入一个’]’即可满足。
数据范围：字符串长度满足的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}