【每日一题20221008】有效的小括号对

:mage: 编写一个函数,该函数接受一个括号字符串,并确定括号的顺序是否有效。如果字符串有效,则函数应返回true,如果字符串无效,则返回false。

示例
“()” => 真
“)(()))” => 假
“(” => 假
“(())((()())())” => 真

制约因素

0 <= 输入长度 <= 100

除了左括号 “(” 和右括号 “)” 之外,输入可以包含任何有效的ASCII字符。此外,输入字符串可能为空和/或根本不包含任何括号。不要将其他形式的括号视为括号(例如[ ]、{ }、< >)。

题目难度:一般
题目来源: Valid Parentheses | Codewars

def valid_parentheses(s: str) -> bool:
    #your code here
    return False

assert valid_parentheses("  (") == False
assert valid_parentheses(")test") == False
assert valid_parentheses("") == True
assert valid_parentheses("hi())(") == False
assert valid_parentheses("hi(hi)()") == True
def valid_parentheses(s: str) -> bool:
    ind = 0
    for i in s:
        if i == '(':
            ind += 1
        elif i == ')':
            ind -= 1
        if ind < 0:
            return False
    if ind != 0:
        return False
    return True

assert valid_parentheses("  (") == False
assert valid_parentheses(")test") == False
assert valid_parentheses("") == True
assert valid_parentheses("hi())(") == False
assert valid_parentheses("hi(hi)()") == True
def valid_parentheses(s: str) -> bool:                                                                            
    bracket_dict = {")": "("}                                       
    stack = []                                                      
    for i in s:                                                     
        if i in bracket_dict:                                       
            if len(stack) > 0 and bracket_dict[i] == stack[-1]:     
                stack.pop()                                         
            else:                                                   
                return False                                        
        elif i in bracket_dict.keys() or i in bracket_dict.values():
            stack.append(i)                                         
    return not stack                                                
1 Like
def valid_parentheses(s: str) -> bool:
    if s=='':return True
    while '()' in s:
        s=s.replace('()','')
        if '(' in s and ')' in s and s.index('(')<s.index(')'):return True
        else:return False
    return False
assert valid_parentheses("hi(hi)(1)") == True

这个测试用例无法通过

新修改了一种
def valid_parentheses(s: str) -> bool:
    if s == '': return True
    list1,list2=[],[]
    for i in s:
        if i=='(':
            num=s.index(i)
            list1.append(num)
            s=s.replace('(','x',1)
        elif i==')':
            num1=s.index(i)
            list2.append(num1)
            s=s.replace(')', 'x', 1)
    if len(list1)==len(list2) and set(list(map(lambda x, y: x < y, list1, list2)))=={True}:
        return True
    else:
        return False

是的,谢老师指出

def valid_parentheses(string):
    cn=0
    for i in string:
        if i=="(":
            cn+=1
        elif i==")" :
            cn-=1
        if cn<0:
            return False
    return cn==0
def valid_parentheses(s: str) -> bool:
    # your code here
    pure_s = ""
    if 0 <= len(s) <= 100:
        for sub_str in s:
            if sub_str in "()":
                pure_s += sub_str
        while "()" in pure_s:
            pure_s = pure_s.replace("()", "")
        return len(pure_s) == 0
    return False

class Stack:
    def __init__(self):
        self.stack = []

    def push(self,val):
        self.stack.append(val)

    def pop(self):
        return self.stack.pop()

    def top(self):
        return self.stack[-1]

    def size(self):
        return len(self.stack)

    def isEmpty(self):
        return self.stack == []

def valid_parentheses(s: str) -> bool:
    #your code here
    st = Stack()
    for i in s:
        if i == '(':
            st.push(i)
        elif i == ')':
            if st.isEmpty():
                st.push(i)
            if st.top() == '(':
                st.pop()
    if st.isEmpty():
        return True
    else:
        return False
def valid_parentheses(s: str) -> bool:
    num_i = 0
    for i in s:
        if i == "(":
            num_i += 1
        if i == ")":
            num_i -= 1
        if num_i < 0:  # 括号对出现以“)”开头的,括号的顺序无效,
            return False
    if num_i == 0:  # 出现成对的括号或没有括号,返回True
        return True
    else:  # 出现不成对的括号,返回False,如"  ("
        return False


assert valid_parentheses("  (") == False
assert valid_parentheses(")test") == False
assert valid_parentheses("") == True
assert valid_parentheses("hi())(") == False
assert valid_parentheses("hi(hi)()") == True

import re
def valid_parentheses(s: str):
    i=0
    left_index = [i.start() for i in re.finditer("\(",s)]
    right_index=[i.start() for i in re.finditer("\)",s)]
    if len(left_index)==len(right_index):
        while i<len(left_index):
            if left_index[i]<right_index[i]:
                i+=1
                continue

            elif left_index[i]>right_index[i]:
                return False
         
        return True

    else:
        return False
关闭