每天一道LeetCode-----括号匹配
Valid Parentheses
原题链接Valid Parentheses
意思是判断是否满足匹配关系，使用栈遍历一遍即可
class Solution {
public:bool isValid(string s) {std::stack<char> st;for(int i = 0; i < s.size(); ++i){char ch = s.at(i);if(ch == '(' || ch == '[' || ch == '{')st.push(ch);else if(st.size() > 0 && ((ch == ')' && st.top() == '(') || (ch == ']' && st.top() == '[') || (ch == '}' && st.top() == '{')))st.pop();elsereturn false;}return st.size() == 0;}
};Generate Parentheses
原题链接Generate Parentheses
意思是给定n，生成所有可能的匹配括号组合
可以直接根据当前左括号的剩余数量判断是否需要添加左括号，以及是否需要添加右括号
- 如果左括号不足n个，可以添加左括号，递归调用
- 如果左括号大于右括号，可以添加右括号，递归调用
代码如下
class Solution {
public:vector<string> generateParenthesis(int n) {vector<string> res;helper(res, "", 0, 0, n);return res;}private:void helper(vector<string>& res, string s, int lhs_n, int rhs_n, int n){if(rhs_n == n){res.push_back(s);return;}if(lhs_n < n)helper(res, s + "(", lhs_n + 1, rhs_n, n);if(lhs_n > rhs_n)helper(res, s + ")", lhs_n, rhs_n + 1, n);}
};Longest Valid Parentheses
原题链接Longest Valid Parentheses
意思是给定一个由”(“,”)”组成的字符串s，找到s最长的子串，要求这个子串的左右括号是正确匹配的
例如
/* 都是括号匹配的字符串 */
()
(())
()()
(()())对于括号匹配问题使用栈是很方便的事情，遇到左括号”(“就入栈，遇到右括号”)”判断栈顶是否有左括号”(“从而判断是否匹配，如果有，则弹出栈顶，继续遍历
但是这种方法只能用于判断一个字符串是否满足匹配条件（Valid Parentheses问题），却没办法找到最长匹配子串.
想要确定最长子串，无非就是直接构造子串，要不就是记录下标。
如果是直接构造子串，是”()()”匹配还是”(())”匹配会有区别，怎样构造string又是一个难题。
如果是记录下标，就需要记录子串开头位置，什么时候是子串的开头也是一个难题。
对于记录下标
0 1 2 3
( ( ) )
遍历的过程中
0, 1依次入栈，到2时弹出1，到3时弹出0，此时最大长度就是3 - 0 + 1 = 40 1 2 3
( ) ( )
遍历的过程中
0入栈，到1时弹出0，长度为1 - 0 + 1 = 2
2入栈，到3时弹出2，长度为3 - 2 + 1 = 2所以对于记录下标的方法，不能计算”()()”这样的匹配的长度，原因是没有记录最开始0的位置，当2入栈3出栈时根本不知道01是否也是匹配的，也就是不知道最开始匹配时的位置，如果直到最开始匹配的位置，到3时弹出2，直接计算3 - start_idx + 1即可。
为了解决这个问题，
在栈的首部添加-1，即初始时栈不为空，栈顶为-1，-1表示起始位置
遍历的过程中，遇到”(“，将索引入栈，遇到”)”，从栈顶弹出一个元素，然后计算”)”的下标和此时栈顶元素的差，即为当前匹配的子串长度
如果遇到”)”时栈中只有-1或者s[stack.top()] == ‘)’，那么将栈顶弹出，将自己的下标入栈，作为起始位置
0 1 2 3 4 5 6 7 8 9
( ) ) ( ( ) ( ) ) )初始栈中元素-1
遍历到0，入栈-1 -> 0
遍历到1，因为栈顶元素不是-1或对应位置不是")"，弹出栈顶，计算长度-1最大长度为1 - (-1) = 2
遍历到2，因为栈顶元素为-1，弹出栈顶，将自己的下标入栈，改变起始位置2
遍历到3，入栈2 -> 3
遍历到4，入栈2 -> 3 -> 4
遍历到5，因为栈顶元素为4，不是-1且s[4] != ')'，弹出栈顶，计算长度2 -> 3最大长度为max(2, 5 - 3) = 2
遍历到6，入栈2 -> 3 -> 6
遍历到7，因为栈顶元素为6，不是-1且s[6] != ')'，弹出栈顶，计算长度2 -> 3最大长度为max(2, 7 - 3) = 4
遍历到8，因为栈顶元素为3，不是-1且s[3] != ')'，弹出栈顶，计算长度2最大长度为max(4, 8 - 2) = 6
遍历到9，入栈2 -> 9
最大长度为6，返回结果初始时-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;}
};本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！