目录

题目要求

代码实现 

---

题目要求

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

---

代码实现

代码演示：

char pairs(char ch)
{if (ch == ')')return '(';if (ch == ']')return '[';if (ch == '}')return '{';return 0;
}bool isValid(char* s)
{int len = strlen(s);int arr[len] = { 0 };int top = 0;// 排除字符串长度为奇数的情况if (len % 2 == 1)return false;for (int i = 0; i < len; i++){if (pairs(s[i]) != 0){if (top == 0 || arr[top-1] != pairs(s[i]))return false;elsetop--;}else{arr[top] = s[i];top++;}}return top == 0;
}

代码解析：

先排除字符串长度为奇数的情况，因为长度为奇数的话，就至少会有一个括号无效
再创建一个 pairs 函数，用来返回对应的括号，和 arr 数组的最后一个元素作比较，相等就消除最后一个元素，利用 top--，不等就说明不是有效括号，直接返回 false
需要注意的是，可以一开始就是右括号，所以在判断的时候要判断 top 是否为 0

代码验证：

为有效括号时：

为无效括号时：

算法的时间和空间复杂度：

for 循环执行了 N 次，每次内部是常数次，且额外创建了长度为 len 的 arr 数组，得出

时间复杂度：O(N)

空间复杂度：O(N)