给定一个字符串s，字符串s只包含以下三种字符: (，*，)，请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:
1.左括号'('必须有对应的右括号')'
2.右括号')'必须有对应的左括号'('
3.左括号必须在对应的右括号前面
4.*可以视为单个左括号，也可以视为单个右括号，或者视为一个空字符
5.空字符串也视为合法的括号字符串
数据范围:
[编程题]合法的括号字符串
import java.util.*;
/**
* NC175 合法的括号字符串
* @author d3y1
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return bool布尔型
*/
public boolean isValidString (String s) {
return solution1(s);
// return solution2(s);
// return solution3(s);
}
/**
* 栈
* @param s
* @return
*/
private boolean solution1(String s){
Stack<Integer> leftStack = new Stack<>();
Stack<Integer> starStack = new Stack<>();
char ch;
for(int i=0; i<s.length(); i++){
ch = s.charAt(i);
if(ch == '('){
leftStack.push(i);
}
else if(ch == '*'){
starStack.push(i);
}
else if(ch == ')'){
if(!leftStack.isEmpty()){
leftStack.pop();
}else if(!starStack.isEmpty()){
starStack.pop();
}else{
return false;
}
}
}
while(!leftStack.isEmpty()){
if(!starStack.isEmpty() && leftStack.peek()<starStack.peek()){
leftStack.pop();
starStack.pop();
}else{
return false;
}
}
return true;
}
/**
* 贪心
* @param s
* @return
*/
private boolean solution2(String s){
// 待消除左括号的最小个数
int minLeft = 0;
// 待消除左括号的最大个数
int maxLeft = 0;
for(char ch: s.toCharArray()){
if(ch == '('){
minLeft++;
maxLeft++;
}
else if(ch == '*'){
// * -> )
if(minLeft > 0){
minLeft--;
}
// * -> (
maxLeft++;
}
else if(ch == ')'){
if(minLeft > 0){
minLeft--;
}
// 已经没有'('或'*'与当前')'匹配
if(maxLeft == 0){
return false;
}
maxLeft--;
}
}
return minLeft==0;
}
/**
* 动态规划
*
* dp[i][j]表示子串s[i,j]是否为合法的括号字符串
*
* len=1:
* dp[i][i] = true , s.charAt(i) == '*'
*
* len=2:
* dp[i][i+1] = true , (currCh=='('||currCh=='*') && (nextCh==')'||nextCh=='*')
*
* len>=3:
* dp[i][j] = dp[i+1][j-1] , (leftCh=='('||leftCh=='*') && (rightCh==')'||rightCh=='*')
* dp[i][j] = dp[i][k]&&dp[k+1][j] , i<=k<j&&!dp[i][j]
*
* @param s
* @return
*/
private boolean solution3(String s){
int n = s.length();
boolean[][] dp = new boolean[n][n];
// len=1 -> *
for(int i=0; i<n; i++){
if(s.charAt(i) == '*'){
dp[i][i] = true;
}
}
// len=2 -> () (* *) **
char currCh,nextCh;
for(int i=0; i+1<n; i++){
currCh = s.charAt(i);
nextCh = s.charAt(i+1);
if((currCh=='('||currCh=='*') && (nextCh==')'||nextCh=='*')){
dp[i][i+1] = true;
}
}
// len>=3
char leftCh,rightCh;
for(int i=n-3; i>=0; i--){
for(int j=i+2; j<n; j++){
leftCh = s.charAt(i);
rightCh = s.charAt(j);
// (())
if((leftCh=='('||leftCh=='*') && (rightCh==')'||rightCh=='*')){
dp[i][j] = dp[i+1][j-1];
}
// ()()
// for(int k=i; k<j&&!dp[i][j]; k++){
// dp[i][j] = dp[i][k]&&dp[k+1][j];
// }
for(int k=i; k<j; k++){
if(dp[i][j]){
break;
}
dp[i][j] = dp[i][k]&&dp[k+1][j];
}
}
}
return dp[0][n-1];
}
}
发表于 2025-01-30 14:00:52
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return bool布尔型
*/
public boolean isValidString (String s) {
if (s.length() == 0) {
return true;
}
LinkedList<Integer> leftStack = new LinkedList<>();
LinkedList<Integer> starStack = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(') {
leftStack.push(i);
} else if (ch == '*') {
starStack.push(i);
} else if (ch == ')') {
if (!leftStack.isEmpty()) {
leftStack.pop();
} else if (!starStack.isEmpty()) {
starStack.pop();
} else {
return false;
}
}
}
while (!leftStack.isEmpty() && !starStack.isEmpty()) {
if (leftStack.peek() > starStack.peek()) {
return false;
}
leftStack.pop();
starStack.pop();
}
return leftStack.isEmpty();
}
}
发表于 2024-05-02 20:47:15
回复(0)
/*
借鉴思路：用两个栈分别存储左括号的下标和*的下标（注意是下标，因为要判断左括号在右括号的前面，分别存储能够体现*的灵活性）。
*/
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* @param s string字符串
* @return bool布尔型
*/
public boolean isValidString (String s) {
Stack<Integer> left = new Stack<>();
Stack<Integer> start = new Stack<>();
for(int i=0;i<s.length();i++){
//左括号或者*号分别入栈
if(s.charAt(i) == '('){
left.push(i);
}
if(s.charAt(i) == '*'){
start.push(i);
}
//如果是右括号，先从左括号栈中匹配，不满足再从*栈中匹配。
//匹配：栈不为空，且栈的元素比当前下标小。
if(s.charAt(i) == ')'){
if(!left.isEmpty() && left.peek()<i){
left.pop();
}else{
if(!start.isEmpty() && start.peek()<i){
start.pop();
}else{
return false;
}
}
}
}
//再判断左括号的栈是否为空，用*进行匹配。
while(!left.isEmpty() && !start.isEmpty()){
if(left.peek() < start.peek()){
left.pop();
start.pop();
}else{
return false;
}
}
//如果左括号的栈为空，则合格；否则不合格。
if(left.isEmpty()){
return true;
}else{
return false;
}
}
}
发表于 2023-02-20 10:40:51
回复(0)
可能出现错误的情况只有1、")n个((((..." 2、"(n个((((..)"，n>=0; 因此当出现这两种情况时返回false即可
public boolean isValidString (String s) {
int m=0,n=0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)==')')m--;
else m++;
if(s.charAt(s.length()-1-i)=='(')n--;
else n++;
if(m<0||n<0)return false;
}
return true;
}
发表于 2022-05-14 22:23:11
回复(2)
public boolean isValidString (String s) {
Deque<Integer> de1=new LinkedList<>();
Deque<Integer> de2=new LinkedList<>();
for(int i=0;i<s.length();i++) {
char c=s.charAt(i);
if(c=='(')
de1.push(i);
else if(c=='*')
de2.push(i);
else {
if(de1.size()>0) {
de1.pop();
}else if(de2.size()>0) {
de2.pop();
}else {
return false;
}
}
}
if(de1.size()>de2.size())
return false;
while(de1.size()>0) {
if(de1.pop()>de2.pop())
return false;
}
return true;
}
发表于 2022-01-14 16:47:11
回复(0)
需要正序和倒序遍历两遍，分别把星号当做左括号和右括号。从左往右遍历，把星号视为左括号，在遍历的过程中如果出现左括号数量比右括号数量少就返回false；然后从右往左遍历，把星号视为右括号，在遍历的过程中如果出现右括号数量比左括号少就返回false。两趟遍历下来还没返回false就返回true。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return bool布尔型
*/
public boolean isValidString (String s) {
// write code here
int left = 0, right = 0, star = 0;
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(c == '('){
left ++;
}else if(c == ')'){
right ++;
}else{
star ++;
}
if(left + star < right) return false;
}
left = 0;
right = 0;
star = 0;
for(int i = s.length() - 1; i >= 0; i--){
char c = s.charAt(i);
if(c == '('){
left ++;
}else if(c == ')'){
right ++;
}else{
star ++;
}
if(right + star < left) return false;
}
return true;
}
}
发表于 2021-12-26 22:25:18
回复(1)
问题信息
通过挑战的用户
查看代码-
2022-10-06 20:49:27 -
2022-10-06 19:32:35
-
2022-09-21 17:52:31
-
2022-09-16 05:48:42
-
2022-09-15 18:52:51
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
