网站设计论文框架,动画设计专业大学排名国内,优秀的定制网站建设提供商,河北邯郸特色美食阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路
需要两个栈#xff0c;一个用来保存左括号所在的位置索引#xff0c;一个用来保存星号所在的位置索引。
从左往右遍历字符串#xff0c;如果是左括号或者星号#xff0c;则将位置索引分别入栈#xff0c;如… 阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路
需要两个栈一个用来保存左括号所在的位置索引一个用来保存星号所在的位置索引。
从左往右遍历字符串如果是左括号或者星号则将位置索引分别入栈如果遇到右括号首先用左括号栈中的左括号进行匹配没有左括号则使用星号作为左括号来进行匹配如果二者都为空匹配失败。
右括号匹配完后如果还有余下的左括号没有匹配完那么就需要在左括号右边的星号来作为右括号进行匹配。
最终左括号也匹配完那么字符串有效因为余下的星号可以作为空字符串。
时间复杂度为 O ( n ) O(n) O(n)空间复杂度也为 O ( n ) O(n) O(n)。
3. 代码实现
class Solution {
public:bool checkValidString(string s) {stackint left_stack;stackint star_stack;for (size_t i 0; i s.size(); i) {if (s[i] () {left_stack.push(i);} else if (s[i] *) {star_stack.push(i);} else if (s[i] )) {if (!left_stack.empty()) {left_stack.pop();} else if (!star_stack.empty()) {star_stack.pop();} else {return false;}}}while (!left_stack.empty() !star_stack.empty()) {if (left_stack.top() star_stack.top()) {return false;} else {left_stack.pop();star_stack.pop();}}return left_stack.empty();}
};
