Score of Parentheses
Here is today's problem: https://leetcode.com/problems/score-of-parentheses/description/
The problem can be solved with a recursive (or non-recursive + stack) solution: implement the base case for rule 1. Then check the "middle" string for well-formed brackets (counting the number of open brackets) - if so, then we're talking about rule 3. Otherwise, that's rule 2. That's it! Marcelo.
Given a balanced parentheses string
S, compute the score of the string based on the following rule:()has score 1ABhas scoreA + B, where A and B are balanced parentheses strings.(A)has score2 * A, where A is a balanced parentheses string.
Example 1:
Input: "()" Output: 1
Example 2:
Input: "(())" Output: 2
Example 3:
Input: "()()" Output: 2
Example 4:
Input: "(()(()))" Output: 6
Note:
Sis a balanced parentheses string, containing only(and).2 <= S.length <= 50
The problem can be solved with a recursive (or non-recursive + stack) solution: implement the base case for rule 1. Then check the "middle" string for well-formed brackets (counting the number of open brackets) - if so, then we're talking about rule 3. Otherwise, that's rule 2. That's it! Marcelo.
public class Solution
{
public int ScoreOfParentheses(string S)
{
if (String.IsNullOrEmpty(S)) return 0;
if (S.Equals("()")) return 1;
int open = 0;
int firstCloseIndex = -1;
for (int i = 1; i < S.Length - 1; i++)
{
if (S[i] == '(') open++;
if (S[i] == ')') open--;
if (open == -1)
{
firstCloseIndex = i;
break;
}
}
if (open == 0)
{
return 2 * ScoreOfParentheses(S.Substring(1, S.Length - 2));
}
else
{
return ScoreOfParentheses(S.Substring(0, firstCloseIndex + 1)) + ScoreOfParentheses(S.Substring(firstCloseIndex + 1));
}
}
}
Very nice solution, Marcelo! I think the reason why it takes so much time though is because of overlapping problems - you are likely recomputing the score for the same string many times. My brute-force (I'm lazy) and highly unoptimized solution with memoization beats 99% of Python submissions and takes only 36s:
ReplyDeleteimport functools
class Solution:
def scoreOfParentheses(self, S: str) -> int:
@functools.lru_cache(maxsize=None)
def compute(s: str) -> int:
if len(s) <= 2:
return 1 if s == "()" else None # rule #1
if s.startswith(")") or s.endswith("("):
return None
score = compute(s[1:-1])
if score is not None:
return 2 * score # rule #3
for i in range(2, len(s) - 1, 2):
score = compute(s[:i])
if score is None:
continue
score2 = compute(s[i:])
if score2 is None:
continue
return score + score2 # rule #2
return compute(S)
https://gist.github.com/ttsugriy/7631548221260aa3f0c8a214e0b6257e
I bet if you use a hashtable to store computed results you'll drastically improve runtime performance.