刷题笔记06-19 (1)

括号匹配（栈思想）

题目如下

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

第一种方法

时间复杂度O(n),空间复杂度O(n)
解题思路：
总体来说，开闭括号应该进行逆序匹配。最后被找到的开括号应该匹配最近的闭括号，最先被找到的开括号应当匹配最后找到的闭括号。这符合我们栈的先进后出的概念。
首先构造一个开闭括号之间的映射表和空栈，为了不从空列表中pop值，在栈中先添加一个空字符串。遍历整个字符串，如果发现开括号，则把闭括号推入栈中。如果是闭括号的，且此闭括号与栈顶的闭括号不匹配的话，则是无效的括号匹配。最后如果栈没空的话，则是无效匹配，如果栈空了的话，则匹配成功。

def parenthesis_match(text):
    matching_dict = {"(":")","{":"}","[":"]"}
    #use the "" in the stack so there is no pop from empty list
    matching_stack = [""]
    for i in text:
        if i in matching_dict:
            matching_stack.push(matching_dict[i])
        elif i in matching_dict.values() and i != matching_stack.pop():
            return False
    return matching_stack.items == [""]

第二种方法

解题思路：
和第一种方法大同小异，如果为开括号，则推入栈中。如果是闭括号，首先检查栈是否为空，如果为空，返回False。然后检查是否和栈顶的开括号相同，如果相同，则pop掉栈顶，如果不同，则返回False值。最后检查栈是否为空栈

def parenthesis_match_flag(text):
    matching_stack = []
    matching_dict = {")":"(","]":"[","}":"{"}
    flag = True
    index = 0
    for i in text:
        if i in matching_dict.values:
            matching_stack.append(i)
        elif i in matching_dict:
            # If there is no opening parenthesis，false
            if len(matching_stack) == 0:
                flag = False
                break
            elif matching_dict[i] == matching_stack[-1]:
                matching_stack.pop()
            else:
                flag = False
                break
        else:
            continue
    # if the stack is not empty, not match
    if matching_stack != []:
        flag = False
    return flag