每天一道LeetCode-----括号匹配
Valid Parentheses
原題鏈接Valid Parentheses
意思是判斷是否滿足匹配關系,使用棧遍歷一遍即可
Generate Parentheses
原題鏈接Generate Parentheses
意思是給定n,生成所有可能的匹配括號組合
可以直接根據當前左括號的剩余數量判斷是否需要添加左括號,以及是否需要添加右括號
- 如果左括號不足n個,可以添加左括號,遞歸調用
- 如果左括號大于右括號,可以添加右括號,遞歸調用
代碼如下
Longest Valid Parentheses
原題鏈接Longest Valid Parentheses
意思是給定一個由”(“,”)”組成的字符串s,找到s最長的子串,要求這個子串的左右括號是正確匹配的
例如
對于括號匹配問題使用棧是很方便的事情,遇到左括號”(“就入棧,遇到右括號”)”判斷棧頂是否有左括號”(“從而判斷是否匹配,如果有,則彈出棧頂,繼續遍歷
但是這種方法只能用于判斷一個字符串是否滿足匹配條件(Valid Parentheses問題),卻沒辦法找到最長匹配子串.
想要確定最長子串,無非就是直接構造子串,要不就是記錄下標。
如果是直接構造子串,是”()()”匹配還是”(())”匹配會有區別,怎樣構造string又是一個難題。
如果是記錄下標,就需要記錄子串開頭位置,什么時候是子串的開頭也是一個難題。
對于記錄下標
所以對于記錄下標的方法,不能計算”()()”這樣的匹配的長度,原因是沒有記錄最開始0的位置,當2入棧3出棧時根本不知道01是否也是匹配的,也就是不知道最開始匹配時的位置,如果直到最開始匹配的位置,到3時彈出2,直接計算3 - start_idx + 1即可。
為了解決這個問題,
在棧的首部添加-1,即初始時棧不為空,棧頂為-1,-1表示起始位置
遍歷的過程中,遇到”(“,將索引入棧,遇到”)”,從棧頂彈出一個元素,然后計算”)”的下標和此時棧頂元素的差,即為當前匹配的子串長度
如果遇到”)”時棧中只有-1或者s[stack.top()] == ‘)’,那么將棧頂彈出,將自己的下標入棧,作為起始位置
初始時-1是什么
-1是記錄找到的子串開始的位置的前一個位置,初始時默認s[0 : ]是滿足的子串,開始位置前一個位置就是-1,當在匹配的過程中已經將棧中所有”(“都彈出后,最后一個”)”的下標減-1就是這個子串的長度
當遇到不能匹配的”)”時入棧的原因
初始時-1是起始位置,但是在匹配的過程中發現到達某個位置i后匹配不上(棧中沒有”(“了),此時就需要找s[i + 1 : ]這部分最長的匹配子串,類似初始時為-1,此時應該為i
匹配的子串長度為什么是當前索引和棧頂元素的差
初始為-1代表匹配的子串的前一個位置,遍歷的過程中遇到”(“也入棧,表示以當前位置作為匹配的第一個位置的前一個位置,直到遇到”)”,彈出和它匹配的”(“,然后計算這個長度,方法是當前索引減去左邊界的前一個位置
代碼如下
class Solution { public:int longestValidParentheses(string s) {std::stack<int> st;/* 初始將-1入棧,作為起始點 */st.push(-1);int max_len = 0;for(int i = 0; i < s.size(); ++i){/* 如果是'(',直接入棧 */if(s[i] == '(')st.push(i);else{/* * 當遇到')'時,如果棧頂是-1或者棧頂所代表的位置是')'* 就需要更換起始位置,代表前面已經匹配完了,從后面開始匹配*/if(st.top() == -1 || s[st.top()] == ')'){st.pop();st.push(i);}/* * 如果棧頂元素所代表的是'(',直接彈出,然后計算和此時棧頂的差*/else{st.pop();max_len = std::max(max_len, i - st.top());}}}return max_len;} };總結
以上是生活随笔為你收集整理的每天一道LeetCode-----括号匹配的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 每天一道LeetCode-----删除链
- 下一篇: muduo网络库学习(一)对io复用的封