leetcode 20 有效的括号

淡淡的烟草味﹌ 2022-09-11 00:05 202阅读 0赞

前言

题目:20. 有效的括号

参考题解:有效的括号-力扣官方题解


提交代码

思路:使用栈进行括号匹配。

这道题以前我提交过。有趣的是,现在的代码和以前的代码风格不同。

现在提交的代码。代码比较稳妥,偏长。

  1. class Solution {
  2. private:
  3. set<char> all_symbol = {'(',')','{','}','[',']'}; // 需要处理的符号
  4. set<char> left_symbol = {'(','{','['}; // 触发压栈的符号
  5. set<char> right_symbol = {')',']','}'}; // 触发匹配的符号
  6. map<char,char> matchRule = {
  7. {')','('},{'}','{'},{']','['}}; ; // 匹配规则
  8. public:
  9. char matchSymbol(char sym){
  10. // 自行确保传入的sym来自“触发匹配的符号”
  11. return matchRule[sym];
  12. }
  13. bool isValid(string s) {
  14. stack<char> readMatchSymbol;
  15. bool result = true;
  16. for(auto sym : s){
  17. if(all_symbol.count(sym)){ // 判断是否为需要处理的符号
  18. if(left_symbol.count(sym)){ // 是否为需要压栈的符号
  19. readMatchSymbol.push(sym);
  20. }else if(right_symbol.count(sym)){ //是否为需要匹配的符号
  21. if(readMatchSymbol.empty()){
  22. result = false;
  23. break;
  24. }
  25. if(matchSymbol(sym) != readMatchSymbol.top()){
  26. result = false;
  27. break;
  28. }
  29. if(matchSymbol(sym) == readMatchSymbol.top()){
  30. readMatchSymbol.pop();
  31. }
  32. }
  33. }
  34. }
  35. return readMatchSymbol.empty()&&result;
  36. }
  37. };

过去提交的代码。以目的为导向,解决问题先。

  1. class Solution {
  2. private:
  3. map<char,char> parenthes={
  4. {'(',')'},
  5. {'[',']'},
  6. {'{','}'}
  7. };
  8. public:
  9. bool isValid(string str) {
  10. stack<char> s;
  11. for(char tmp : str){
  12. if( parenthes.find(tmp)!=parenthes.end() )
  13. s.push(tmp);
  14. else{
  15. if(!s.empty()){
  16. if( parenthes[s.top()]!=tmp )
  17. return false;
  18. else{
  19. s.pop();
  20. continue;
  21. }
  22. }
  23. else{
  24. return false;
  25. }
  26. }
  27. }
  28. return s.empty()?true:false;
  29. }
  30. };

发表评论

表情:
评论列表 (有 0 条评论,202人围观)

还没有评论,来说两句吧...

相关阅读

    相关 LeetCode20 有效括号

    题目重述 给定一个只包括 ‘(’,’)’,’\{’,’\}’,’\[’,’\]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括

    相关 leetcode:20.有效括号

    题目描述: 给定一个只包括 ‘(’,’)’,’\{’,’\}’,’\[’,’\]’ 的字符串,判断字符串是否有效。 有效字符串需满足: 1. 左括号必须用相同类型的

    相关 LeetCode---20. 有效括号

    有效的括号 给定一个只包括 ‘(’,’)’,’\{’,’\}’,’\[’,’\]’ 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭