55：Valid Parentheses

2019-11-06 08:33:09

字体：大中小

来源：转载

供稿：网友

题目：Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid. The brackets must close in the correct order, “()” and “()[]” are all valid but “(]” and “([)]” are not.

解题代码一：

// 时间复杂度 O(n)，空间复杂度 O(n)class Solution {public: bool isValid(string s) { stack<char> bracket; for (int i = 0; i != s.size(); ++i) { if (s[i] == ')') { if (!bracket.empty() && bracket.top() == '(') bracket.pop(); else return false; } else if (s[i] == ']') { if (!bracket.empty() && bracket.top() == '[') bracket.pop(); else return false; } else if (s[i] == '}') { if (!bracket.empty() && bracket.top() == '{') bracket.pop(); else return false; } else bracket.push(s[i]); }/* if (bracket.empty()) return true; else return false;*/ return bracket.empty(); }};

上面的代码 if… else 语句过多，比较冗杂，如果再考虑其它的括号，比如大括号等等，则会更加冗杂，下面的代码则更为精简

// 时间复杂度 O(n)，空间复杂度 O(n)class Solution {public: bool isValid(string s) { string left = "([{"; string right = ")]}"; stack<char> bracket; for (int i = 0; i != s.size(); ++i) { auto index = right.find(s[i]); if (index != string::npos) { // s[i] 属于 ')', ']' 或 '}' if(!bracket.empty() && bracket.top() == left[index]) bracket.pop(); else return false; } else bracket.push(s[i]); }/* if (bracket.empty()) return true; else return false;*/ return bracket.empty(); }}

上一篇：《Linux内核设计与实现》——内存管理

下一篇：入门级爬虫抓取豆瓣top250 的电影信息