【题号20】
题目描述:
给定一个只包括'(',')','{','}','[',']'的字符串,判断字符串是否有效。
括号必须以正确的顺序关闭,"()"和"()[]{}"是有效的但是"(]"和"([)]"不是。
解题思路:栈思想。
遍历字符串,用一个数组作为栈;
当遇到左括号时,则将其保存到数组中;
当遇到右括号时,则将数组中最后一个元素与之匹配,若可配对,则删除该元素,若不能配对,则字符串无效;
最后当字符串遍历结束后,若数组长度为0,则说明括号都已配对,否则字符串无效。
代码实现:
class Solution {
public:
bool isValid(string s) {
vectorarr;
int j=0;
for(int i=0;i
if(s[i]=='(' || s[i]=='{' || s[i]=='['){
arr.push_back(s[i]);
j++;
}
if(s[i]==')'){
if(j==0 || arr[j-1]!='(') return false;
arr.pop_back();
j--;
}
if(s[i]=='}'){
if(j==0 || arr[j-1]!='{') return false;
arr.pop_back();
j--;
}
if(s[i]==']'){
if(j==0 || arr[j-1]!='[') return false;
arr.pop_back();
j--;
}
}
if(arr.size()!=0)return false;
return true;
}
};
领取专属 10元无门槛券
私享最新 技术干货