Python：每日一题 232（答题有奖）

zltzlt

今天的题目（有点小难哦）：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。e$ *7!!Q
3. 注意空字符串可被认为是有效字符串。

这道题已结束，进入奖励阶段。

示例 1：

输入: "()"
输出: True

示例 2：

输入: "()[]{}"
输出: True

示例 3：

输入: "(]"
输出: False

示例 4：

输入: "([)]"
输出: False

示例 5：

输入: "{[]}"
输出: True

我原来的解法：

1. def is_valid(string):
   
2.     list1 = list(string)
   
3.     while list1:
   
4.         if list1.count("(") != list1.count(")"):
   
5.             return False
   
6.         elif list1.count('[') != list1.count("]"):
   
7.             return False
   
8.         elif list1.count("{") != list1.count("}"):
   
9.             return False
   
10.         for i, each in enumerate(list1):
    
11.             if list1[i] == "(":
    
12.                 if list1[i + 1] == ")":
    
13.                     list1.pop(i)
    
14.                     list1.pop(i)
    
15.                 else:
    
16.                     try:
    
17.                         index = list1.index(")")
    
18.                     except ValueError:
    
19.                         return False
    
20.                     return is_valid("".join(list1[i + 1:index]))
    
21.             elif list1[i] == "[":
    
22.                 if list1[i + 1] == "]":
    
23.                     list1.pop(i)
    
24.                     list1.pop(i)
    
25.                 else:
    
26.                     try:
    
27.                         index = list1[i:].index("]")
    
28.                     except ValueError:
    
29.                         return False
    
30.                     return is_valid("".join(list1[i + 1:index]))
    
31.             elif list1[i] == "{":
    
32.                 if list1[i + 1] == "}":
    
33.                     list1.pop(i)
    
34.                     list1.pop(i)
    
35.                 else:
    
36.                     try:
    
37.                         index = list1.index("}")
    
38.                     except ValueError:
    
39.                         return False
    
40.                     return is_valid("".join(list1[i + 1:index]))
    
41.     return True

复制代码

改进后的解法：

1. def fun(string: str):
   
2.     string = string.replace("()", "").replace("{}", "").replace("[]", "")
   
3.     if (string.count("(") != string.count(")") or string.count("[") !=
   
4.             string.count("]") or string.count("{") != string.count("}")):
   
5.         return False
   
6.     for i in range(2, len(string)):
   
7.         try:
   
8.             if (string[string.index("(") + i] == ")" or
   
9.                     string[string.index("[") + i] == "]" or
   
10.                     string[string.index("{") + i] == "}"):
    
11.                 return False
    
12.         except ValueError:
    
13.             return False
    
14.     return fun(string) if string else True

复制代码

_2_

就这个示例5不太好实现

zltzlt

_2_ 发表于 2019-8-30 18:15
就这个示例5不太好实现

这个有点伤脑筋我做了好久

_2_

zltzlt 发表于 2019-8-30 18:16
这个有点伤脑筋我做了好久

自己挖坑自己跳
很佩服版主的精神

永恒的蓝色梦想

如果没有例二的话，直接eval()就可以

1. dictionary={'[':']','{':'}','(':')'}
   
2. def function(string):
   
3.         while string!='':
   
4.                 try:
   
5.                         k=string.index(dictionary[string[0]])
   
6.                 except:
   
7.                         return False
   
8.                 string=string[1:k]
   
9.                 if not function(string):
   
10.                         return False
    
11.         return True

复制代码

小香蕉2009

我只学了元组()和列表[],{}这是啥玩意

zltzlt

小香蕉2009 发表于 2019-8-30 18:49
我只学了元组()和列表[],{}这是啥玩意

{} 是集合或者字典

zltzlt

永恒的蓝色梦想 发表于 2019-8-30 18:46
如果没有例二的话，直接eval()就可以

你这个这么简单，我的三十多行

小香蕉2009

你的标题有问题，因为只要是引号里的都是字符串，这对不对称有什么关系呢

zltzlt

小香蕉2009 发表于 2019-8-30 18:55
你的标题有问题，因为只要是引号里的都是字符串，这对不对称有什么关系呢

看我的题目

永恒的蓝色梦想

zltzlt 发表于 2019-8-30 18:52
你这个这么简单，我的三十多行

老哥你怎么写的

小香蕉2009

zltzlt 发表于 2019-8-30 18:49
{} 是集合或者字典

哦

小香蕉2009

zltzlt 发表于 2019-8-30 18:49
{} 是集合或者字典

你确定我这个小白看得懂

小香蕉2009

_2_ 发表于 2019-8-30 18:15
就这个示例5不太好实现

你确定我这个小白看得懂你太为难我了，我要去碎片化学习，不理你

永恒的蓝色梦想

忽然又想到一种方法，尽管歪门邪道吧……
改一下

1. def func(t):
   
2.         try:
   
3.                 eval(''.join((i+',' if i in(']','}',')') else i for i in t)))
   
4.         except SyntaxError:
   
5.                 return False
   
6.         except:
   
7.                 pass
   
8.         return True

复制代码

zltzlt

永恒的蓝色梦想 发表于 2019-8-30 19:08
忽然又想到一种方法，尽管歪门邪道吧……

天哪

永恒的蓝色梦想

小香蕉2009 发表于 2019-8-30 19:04
你确定我这个小白看得懂

如果里面没有冒号则为集合，有则为字典
为空则为字典

zltzlt

永恒的蓝色梦想 发表于 2019-8-30 19:08
忽然又想到一种方法，尽管歪门邪道吧……
改一下

except:
                pass

完全可以去掉

塔利班

忘了原来时间复杂度小的怎么写了，应该还是指针移动来去的

1. def fun232(x):
   
2.     while True:
   
3.         t=x
   
4.         x=x.replace('()','').replace('{}','').replace('[]','')
   
5.         if x==t:
   
6.             break
   
7.     return x==''

复制代码

panheng

题目没太懂 那种嵌套必须是以中心对称吗？ "（()[]{}）"  返回True吗？