20. Valid Parentheses

萬分抱歉，最近在忙工作和應聘，周更拖成了月更。請相信我，在不斷挖坑的同時，我一定會把之前的坑填上的。實踐證明，刷LeetCode題目真的對面試很有幫助的。上個月去菊廠兩個部門面試測試工程師，兩個部門面試下來感覺菊廠技術方面最注重兩點，一個是對於測試流程的熟悉，另外一個就是自動化能力，也就主要是Python語言的應用能力，前者靠忽悠，後者就要你現場寫代碼了。我也就半年前刷了三分之一的題目，沒想到就給撞到了，對，就是這道（其實他們出的題目要更簡化一點，只涉及到一種括弧類型）。容我再補充句題外話，如果你面試的崗位和你之前的崗位有相關性的話，他們會問你很多很細的問題，這就要看你的紮實積累和臨場應變能力了。雲網路部門的經理拉著我談了一個多鐘頭，而且經常會針對我的回答提出一些細枝末節的問題。當這些你都能瀟洒面對過去，技術面便一點也不成問題了。最後提醒一下，如果有同學去同時面試某些大公司的多個部門時，一定要問清楚，這些offer是不是衝突的，會被會拒了第一個offer第二個就要等一年了，不說了，都是淚。

本題是 Leetcode Top 100 liked questions 中的第十一題。

10. 20. Valid Parentheses

Easy

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

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

題意

給出一串僅僅包涵大中小三中類型括弧字元串，請判斷字元串是否符合正規用法。

分析

題意一目了然，我們僅需要知道判斷表達式是否合法的根據就行了，也就是有開又閉，先開後閉（注意題目沒有要求檢查嵌套關係喲，嵌套的一律不合法）。這裡面涉及到一種前後對照的關係，所以定然需要一種方法可以把前面的括弧狀態存儲下來以方便後面去判斷合法性，沒錯，就是你了，堆棧。

代碼實現

class Solution(object): def isValid(self, s): """ : type s: str : rtype: bool """ #define a stack to retore left parentheses self.stack=list() #define a dictionanry to check if right and left can match self.dic={}:{,]:[,):(} for i in s: if i in ({,[,(): self.stack.append(i) else: if not self.stack or self.dic[i] != self.stack[-1]: return False else: self.stack.pop() if self.stack: return False return True

Python Tips

是不是超級水，我面試的時候只用判斷一個小括弧就行了，他們可能只想看你會不會python基礎吧，不要求太高的演算法能力。stack前面談過了，這裡就不談了。

推薦閱讀：