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

zltzlt

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

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

有效字符串需满足：

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

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

示例 1：

输入: "()"
输出: True

示例 2：

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

示例 3：

输入: "(]"
输出: False

示例 4：

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

示例 5：

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

我原来的解法：

def is_valid(string):
    list1 = list(string)
    while list1:
        if list1.count("(") != list1.count(")"):
            return False
        elif list1.count('[') != list1.count("]"):
            return False
        elif list1.count("{") != list1.count("}"):
            return False
        for i, each in enumerate(list1):
            if list1[i] == "(":
                if list1[i + 1] == ")":
                    list1.pop(i)
                    list1.pop(i)
                else:
                    try:
                        index = list1.index(")")
                    except ValueError:
                        return False
                    return is_valid("".join(list1[i + 1:index]))
            elif list1[i] == "[":
                if list1[i + 1] == "]":
                    list1.pop(i)
                    list1.pop(i)
                else:
                    try:
                        index = list1[i:].index("]")
                    except ValueError:
                        return False
                    return is_valid("".join(list1[i + 1:index]))
            elif list1[i] == "{":
                if list1[i + 1] == "}":
                    list1.pop(i)
                    list1.pop(i)
                else:
                    try:
                        index = list1.index("}")
                    except ValueError:
                        return False
                    return is_valid("".join(list1[i + 1:index]))
    return True

改进后的解法：

def fun(string: str):
    string = string.replace("()", "").replace("{}", "").replace("[]", "")
    if (string.count("(") != string.count(")") or string.count("[") !=
            string.count("]") or string.count("{") != string.count("}")):
        return False
    for i in range(2, len(string)):
        try:
            if (string[string.index("(") + i] == ")" or
                    string[string.index("[") + i] == "]" or
                    string[string.index("{") + i] == "}"):
                return False
        except ValueError:
            return False
    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()就可以

dictionary={'[':']','{':'}','(':')'}
def function(string):
        while string!='':
                try:
                        k=string.index(dictionary[string[0]])
                except:
                        return False
                string=string[1:k]
                if not function(string):
                        return False
        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不太好实现

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

永恒的蓝色梦想

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

def func(t):
        try:
                eval(''.join((i+',' if i in(']','}',')') else i for i in t)))
        except SyntaxError:
                return False
        except:
                pass
        return True

zltzlt

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

天哪

永恒的蓝色梦想

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

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

zltzlt

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

except:
                pass

完全可以去掉

塔利班

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

def fun232(x):
    while True:
        t=x
        x=x.replace('()','').replace('{}','').replace('[]','')
        if x==t:
            break
    return x==''

panheng

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