给定一个字符串s,字符串s只包含以下三种字符: (,*,),请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:
1.左括号'('必须有对应的右括号')'
2.右括号')'必须有对应的左括号'('
3.左括号必须在对应的右括号前面
4.*可以视为单个左括号,也可以视为单个右括号,或者视为一个空字符
5.空字符串也视为合法的括号字符串
数据范围:
"()()"
true
"((*)"
true
"(*)"
true
"(((*)"
false
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; } }
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; }
function isValidString(s) { var stack = []; var sArr = s.split(''); // 处理右括号 for(var i = 0; i < sArr.length; i++) { var item = sArr[i]; if(item === '(' || item === '*') { stack.push(item); } // 遇到右括号时,从栈里面去找最近的左括号,若找不到,则找最近的*号, 若依然找不到,则字符串无效 if(item === ')') { var _stack = [...stack].reverse(); // 若栈为空,则字符串无效 if(_stack.length === 0) { stack.push(-1); break; } // 寻找最近的左括号或左星号,都没有,则字符串无效 var index = _stack.indexOf('(') > -1 ? _stack.indexOf('(') : _stack.indexOf('*'); if(index === -1) { break; } // 将最近的左括号或左星号替换为空 stack[stack.length - index -1] = ''; } } stack = stack.filter(item => item !== ''); // stack数组情况,可能存在多余的左括号( 和 多余的星号,将(和*相互抵消 for(var j = stack.length - 1; j >= 0; j--) { if(stack[j] === '(') { // 检查元素右侧是否存在星号,若存在,则将 var starIndex = stack.indexOf('*',j); if(starIndex > -1) { stack[j] = ''; stack[starIndex] = ''; } else { break; } } } return stack.join('').replaceAll('*','').length === 0; }
#include <stack> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return bool布尔型 */ bool isValidString(string s) { // write code here if (s.size() == 0) return true; // 先清除可以匹配的(),如(*())(()))变成(*)) stack<char> chs; for (char ch : s) { if (ch == ')') { if (chs.empty()) { return false; } else if (chs.top() == '(') { chs.pop(); } else { chs.push(ch); } } else { chs.push(ch); } } // 如果末尾为(,必非法 if (!chs.empty() && chs.top() == '(') return false; // 连接剩下的字符串 s = ""; while (!chs.empty()) { s = chs.top() + s; chs.pop(); } return isMatch(s); } // 判断字符串是否能够匹配,即*适当转变之后能够匹配() bool isMatch(string s) { /** * 判断是否存在)(的情况,存在则分开字符串分别再次匹配 * 如*)(((*),看似3个(,2个),可以将一个*转变为),但是它非法 * 此时需将*)和(((*)分别判断,前者匹配后者否,所以非法 */ int pos = -1; for (int i = 1; i < s.size(); i++) { if (s[i - 1] == ')' && s[i] == '(') { pos = i; break; } } /** * 不存在)(的情况,直接判断是否匹配, * 只需(的数量与)的数量差值不大于*的数量, * 则*可以适当转变(或)使得匹配 */ if (pos < 0) { int left = 0, right = 0, mid = 0; for (char ch : s) { if (ch == '(') { left++; } else if (ch == ')') { right++; } else if (ch == '*') { mid++; } } return abs(left - right) <= mid; } // 存在)(的情况,分开字符串分别再次匹配,即递归 string left = s.substr(0, pos); string right = s.substr(pos, s.size() - pos); return isMatch(left) && isMatch(right); } };
function isValidString( s ) { // write code here // 根据星号数量和左右括号数量最少的数量的和和左右括号数量最多的数量作比较来淘汰不符合的字符 let leftCount = s.match(/\(/g)?s.match(/\(/g).length:0; let rightCount = s.match(/\)/g)?s.match(/\)/g).length:0; let xingCount = s.match(/\*/g)?s.match(/\*/g).length:0; if(xingCount+Math.min(leftCount,rightCount) < Math.max(leftCount,rightCount)){ return false } else{ // 定义三个匹配模式匹配可以成对的括号 let pattern1 = /\((\**)\)/;//中间的括号用于捕获 let pattern2 = /\(\*/;//注意,这里不加g,是为了每次都能从头匹配 let pattern3 = /\*\)/; while(pattern1.test(s)){ s = s.replace(/\((\**)\)/g,'$1');//$1是捕获的第一个数据 } while(pattern2.test(s)){ s = s.replace(/\(\*/g,''); } while(pattern3.test(s)){ s = s.replace(/\*\)/g,''); } if(/^\**$/.test(s)){ return true }else{ return false } } }
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param s string字符串 # @return bool布尔型 # class Solution: def isValidString(self , s: str) -> bool: # write code here star_stack = [] symbol_stack = [] for i in range(len(s)): if s[i:i+1] == '(': symbol_stack.append([i,'(']) elif s[i:i+1] == '*': star_stack.append([i,'*']) else: if symbol_stack: symbol_stack.pop() continue elif len(symbol_stack) == 0 and star_stack: star_stack.pop() continue else: return False while symbol_stack: if len(star_stack) == 0: return False if symbol_stack.pop()[0] > star_stack.pop()[0]: return False return True
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return bool布尔型 */ public boolean isValidString (String s) { // write code here Deque<Integer> stack1 = new ArrayDeque<>(); Deque<Integer> stack2 = new ArrayDeque<>(); for(int i = 0; i < s.length(); i++) { switch(s.charAt(i)) { case '(': stack1.offerLast(i); break; case '*': stack2.offerLast(i); break; case ')': if(!stack1.isEmpty()) { stack1.pollLast(); } else { if(stack2.isEmpty()) return false; stack2.pollLast(); } break; } } while(!stack1.isEmpty()) { if(stack2.isEmpty()) break; if(stack1.getLast() > stack2.getLast()) break; stack1.pollLast(); stack2.pollLast(); } return stack1.isEmpty(); } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return bool布尔型 */ public boolean isValidString (String s) { // write code here LinkedList<Integer> list = new LinkedList<Integer>(); LinkedList<Integer> stars = new LinkedList<Integer>(); for(int i = 0; i < s.length(); i++){ if(s.charAt(i) == ')'){ if (list.size() == 0){ if(stars.size() > 0){ stars.removeFirst(); } else { return false; } } else { list.removeFirst(); } } else { if(s.charAt(i) == '*'){ stars.addFirst(i); } else list.addFirst(i); } } //检查 while(list.size() != 0) { if(stars.size() > 0 && stars.getFirst() > list.getFirst()){ stars.removeFirst(); list.removeFirst(); } else { return false; } } return true; } }
class Solution: def isValidString(self , s: str) -> bool: l = [] star = [] for i in range(len(s)): if s[i] == '(': l.append(i) elif s[i] == '*': star.append(i) elif s[i] == ')': if l: l.pop() elif star: star.pop() else: return False if len(l) > len(star): return False i = j = 0 while l and j < len(star): if l[i] < star[j]: l.pop(i) star.pop(j) else: j += 1 if l == []: return True else: return False
public boolean isValidString(String s) { char[] chars = s.toCharArray(); Stack<Integer> left = new Stack<>(); Stack<Integer> star = new Stack<>(); for (int i = 0; i < chars.length; i++) { if (chars[i] == '(') { left.push(i); } else if (chars[i] == '*') { star.push(i); } else { if (left.isEmpty() && star.isEmpty()) { return false; } else if (!left.isEmpty()) { left.pop(); } else { star.pop(); } } } while (!left.isEmpty() && !star.isEmpty()) { if (left.peek() < star.peek()) { left.pop(); star.pop(); } else { return false; } } return left.isEmpty(); }
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; } } }
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param s string字符串 # @return bool布尔型 # class Solution: def isValidString(self , s: str) -> bool: # write code here #定义2个空栈,一个用来存放左括号,一个用来存放*号,遇到右括号的时候先出stack1,当stack1为空的时候,再出stack2,当stack2为空的时候,返回False #print("ok") stack1=[] stack2=[] #print(s) for x in range(len(s)): if s[x] == "(": stack1.append(x) elif s[x]=="*": stack2.append(x) elif s[x]==")": if len(stack1)>0: stack1.pop() elif len(stack2)>0: stack2.pop() else: return False print(stack1) print(stack2) #如果比较完,stack1等于0的话,说明括号已经完全匹配了,返回true即可 if len(stack1) ==0: return True #如果说stack1大于0,并stack2大于0.stack1的元素比stack2多,需要比较stack1中的括号的位置与*的索引顺序,小于*Hao的索引才能匹配,大于星号则永远不能匹配,当stack1中的元素pop完退出while循环或者当stack1中的元素的pop值比stack2还大,需要将pop出的元素append回来直接break出循环体,最后通过比较stack1中的元素数量如果为空了,就匹配成功了说明,否则匹配失败 elif len(stack1)>0 and len(stack2)>0 and len(stack1)<=len(stack2) : while len(stack1)>0 : x=int(stack1.pop()) y=int(stack2.pop()) print(stack1,x,y) if x<y: pass else: stack1.append(x) break print(stack1) if len(stack1) ==0: return True else: return False else: return False
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param s string字符串 # @return bool布尔型 # class Solution: def isValidString(self , s: str) -> bool: # write code here left = [] star =[] s = s[1:-1] # 把所有(和*当左边界压入栈 for i in range(len(s)): if s[i] == '(': left.append(i) elif s[i] == '*': star.append(i) else: # )右括号出栈 if len(left): left.pop() elif len(star): star.pop() # 右括号不够匹配了,返回false else: return "false" # 然后右括号匹配 while len(left) and len(star): if len(left)>len(star): return "false" if left.pop() > star.pop(): return "false" return "true" print(Solution().isValidString(input()))翻译过来的为啥输出不通过