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

兴趣爱好交流 每日一题
1

: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
2 
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
3 
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 个赞
4 
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
5 
assert valid_parentheses("hi(hi)(1)") == True

这个测试用例无法通过

6 
新修改了一种
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
7

是的，谢老师指出

8 
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
9 
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
10 

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
11 
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
12 
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
13 
def valid_parentheses(string):
    #your code here
    l_list = []
    if 0 <= len(string) <= 100:
        l_count = string.count('(')
        r_count = string.count(')')
        if l_count == 0 and r_count == 0:
            return True
        elif l_count == r_count:
            for i in string:
                if i == '(':
                    l_list.append(i)
                elif i == ')':
                    try:
                        l_list.pop(-1)
                    except Exception:
                        return False
            return True
    return False
14 
def valid_parentheses(s: str) -> bool:
    if s.count("(")!=s.count(")"):
        return False
    else:
        str_res=''.join([s[i] for i in range(len(s)) if s[i]=="(" or s[i]==")"])
        while "(" in str_res:
            left_index=str_res.index("(")
            right_index=str_res.index(")")
            if right_index>left_index:
                str_res=str_res[:left_index]+str_res[left_index+1:right_index]+str_res[right_index+1:]
            else:
                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
assert valid_parentheses("(())((()())())") == True