给定一个字符串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; }
public boolean isValidString (String s) { int low = 0; int high = 0; for (char c : s.toCharArray()) { if (c == '(') { // 对于 '(',两个计数器都增加 low++; high++; } else if (c == ')') { // 对于 ')',两个计数器都减少 low--; high--; } else if (c == '*') { // 对于 '*',low 可以减少,high 可以增加 low--; high++; } // low 不应该小于 0 if (low < 0) { low = 0; } // 如果 high 变为负数,意味着太多的右括号无法匹配 if (high < 0) { return false; } } // 如果 low 为 0,则说明存在一种可能的 '*' 分配方式使得所有括号都匹配 return low == 0; }
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 } } }
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(); } }
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param s string字符串 # @return bool布尔型 # class Solution: def isValidString(self,s:str) -> bool: # write code here class Stack: def __init__(self) -> None: self.items = [] def isEmpty(self): return self.items == [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def size(self): return len(self.items) s1 = Stack() star_list=[] index, last_index, star_index = 0, 0, 0 pre_index1,pre_index2=0,0 balanced = True while index < len(s) and balanced: char = s[index] if char == '(' : s1.push(char) pre_index1=last_index last_index=max(last_index,index) elif char == '*': star_list.append(char) pre_index2=star_index star_index=max(star_index,index) else: if s1.isEmpty() and star_list == []: balanced = False else: if not s1.isEmpty(): s1.pop() last_index=pre_index1 else: star_list.pop() star_index=pre_index2 index += 1 if s1.isEmpty() and balanced: return True elif s1.size()<=len(star_list) and balanced and star_index>=last_index: 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(); }