leetcode 856. Score of Parentheses 括号的分数-耗时100

Problem: 856. Score of Parentheses 括号的分数

解题过程

耗时100%，两种方案的，1、递归调用即可，2、或者使用栈的，

1、使用栈，耗时100%

int scoreOfParentheses(string s) { if(s=="()") return 1; int n = s.size(), score, ind, sum = 0; stack<pair<int, int>> tk; for(int i = 0; i < n; i++) { if(s[i]=='(') { if(tk.empty() == false) { tk.push({i, tk.top().second << 1}); } else { tk.push({i, 1}); } } else { score = tk.top().second; ind = tk.top().first; tk.pop(); if(i - ind == 1) { sum += score; } } } return sum; } };

2、递归调用Code

class Solution { public: int findclose(string s, int start) { if(s.size() == 2) return 1; stack<char> tk; int n = s.size(); for(int i = start; i < n; i++) { if(s[i]=='(') tk.push('('); else tk.pop(); if(tk.empty() == true) { return i; } } return -1; } int scoreOfParentheses(string s) { if(s=="()") return 1; int n = s.size(), ind, sum = 0; string tmp; for(int i = 0; i < n; i++) { if(s[i]=='(') { ind = findclose(s, i); if(ind - i + 1 == n) { tmp = s.substr(i+1, ind - i - 1); sum = scoreOfParentheses(tmp) * 2; break; } else { tmp = s.substr(i, ind - i + 1); sum += scoreOfParentheses(tmp); i = ind; } } } return sum; } };