算法@LeetCode:ValidParentheses

Log

• 【170418】完成 01 版（Python）提交
• 【170419】完成 01 版笔记
• 【170423】研究参考解法思路并完成笔记

题目

Valid Parentheses

【题目类型备注】

栈, 字符串

提交

01

【语言】

Python

【时间】

170418

【思路】

典型的栈应用：当我们每遇到一个右侧符号（)、]、} 之一）要找配对时，显然是字符串之前找到最近的那个左侧符号（(、[、{ 之一）去看看与之是否配对。也就是说，后输入的（左侧）字符，在进行「配对判断」时，是先出现的。

因此，这符合栈「后进先出」（LIFO）原则，使用栈来完成本题。

另外，还要考虑 2 种情况：

1. 当右侧符号多于左侧符号时：左侧符号被用完，栈已空，还有未配对的右侧符号等待左侧符号，这样的输入不合法
2. 当左侧符号多于右侧符号时：右侧符号已用完，栈未空，还有未配对的左侧符号等待右侧符号，这样的输入不合法

于是有代码如下

【代码】

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        right = [')', ']', '}']
        left = ['(', '[', '{']
        for ch in s:
          if ch in left:
            stack.append(ch)
          elif ch in right:
            if (len(stack) == 0):
              return False
            else:
              maypair = stack.pop()
              if left.index(maypair) != right.index(ch):
                return False

        if len(stack) > 0:
          return False
      
        return True

【结果】

运行时：49 ms

报告链接：https://leetcode.com/submissions/detail/100480839/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 57.48% of python submissions.

00

参考解法：

• Java
  • 1
  • 2
• Python
• C++

上述最优解的思路基本和我的思路是一样的，所以基本上可认为我的解法也是最优解。上述选取的参考解法在细节处理上不同于我的点在于：

1. Java-2 解法中，用字符串来替代「列表」以搜索当前处理的字符的下标
2. Python 解法中，用字典匹配来替代列表下标匹配