|
| 1 | +""" |
| 2 | +We parse the content in the parentheses and evaluate it. |
| 3 | +If the content is empty string then the value is 1. |
| 4 | +Otherwise, the value is the value of the content multiply by 2 |
| 5 | +And we use the exact the same function to evaluate the value of the content (recursion). |
| 6 | +We can know the start and the end of the parentheses (so we can extract the content) by `depth`, which is the level of parentheses. |
| 7 | +
|
| 8 | +Even though this looks efficient the time complexity is high. O(N^depth). |
| 9 | +You can think of a case like this |
| 10 | +``` |
| 11 | +(((((((((( ... content ... )))))))))) |
| 12 | +``` |
| 13 | +Where in every level you have to go through the whole thing again. |
| 14 | +
|
| 15 | +The Space complexity is O(depth). |
| 16 | +Even we only use O(1) in each function, but the recursion takes stack memory of O(depth). |
| 17 | +""" |
| 18 | +class Solution(object): |
| 19 | + def scoreOfParentheses(self, S): |
| 20 | + depth = 0 |
| 21 | + start = 0 |
| 22 | + score = 0 |
| 23 | + for i, s in enumerate(S): |
| 24 | + if s=='(': depth+=1 |
| 25 | + if s==')': depth-=1 |
| 26 | + if depth==0: |
| 27 | + content = S[start+1:i] |
| 28 | + if content == '': |
| 29 | + score+=1 |
| 30 | + else: |
| 31 | + score+=self.scoreOfParentheses(content)*2 |
| 32 | + start = i+1 |
| 33 | + return score |
| 34 | + |
| 35 | +""" |
| 36 | +If we take a closer look, we will notice that `()` are the only structure that provides value, the outer parentheses just add some multiplier. |
| 37 | +So we only need to be concerned with `depth`. |
| 38 | +For level we multiply the inner content by 2, so for each `()`, its value is `1 * 2**depth` |
| 39 | +
|
| 40 | +The time complexity is O(N). |
| 41 | +The space complexity is O(1). |
| 42 | +""" |
| 43 | +class Solution(object): |
| 44 | + def scoreOfParentheses(self, S): |
| 45 | + score = 0 |
| 46 | + depth = 0 |
| 47 | + |
| 48 | + for i, s in enumerate(S): |
| 49 | + if s=='(': |
| 50 | + depth+=1 |
| 51 | + else: |
| 52 | + depth-=1 |
| 53 | + if S[i-1]=='(': |
| 54 | + score+=2**depth |
| 55 | + return score |
0 commit comments