微信 免费 网站/朋友圈广告推广

[ 题目描述 ]：

[ 思路 ]：

• 该题为栈的经典应用
• 遇见左括号即压入栈中，遇见右括号则弹出栈顶元素与其匹配
  • 匹配成功，则继续遍历
  • 匹配不成功，则返回无效
• 期间可能出现，左括号多余右括号(遍历完成后，判断栈是否已清空)，或者右括号比左括号多(遇见右括号，栈中无括号，直接返回false)
• 运行如下
  

bool isValid(char* s) {int top=-1,len=strlen(s);char* stack=(char*)malloc(sizeof(char)*(len));for(int i=0;i<len;i++){if (s[i] == '(' || s[i] == '[' || s[i] == '{') {stack[++top] = s[i];} else {if (top == -1) return false;  // 栈空但遇到右括号char c = stack[top--];if ((s[i] == ')' && c != '(') || (s[i] == ']' && c != '[') || (s[i] == '}' && c != '{')) {return false;}}}free(stack);return top==-1;
}

[ 官方题解 ]：

• 栈，基本同上，增加了一个判断字符串长度是否为偶数，偶则可能匹配，奇数则一定不匹配，因为括号是成双出现的