Score of Parentheses

Here is today's problem: https://leetcode.com/problems/score-of-parentheses/description/

Given a balanced parentheses string S, compute the score of the string based on the following rule:
  1. () has score 1
  2. AB has score A + B, where A and B are balanced parentheses strings.
  3. (A) has score 2 * 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:
  1. S is a balanced parentheses string, containing only ( and ).
  2. 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));
  }
 }
}

Comments

  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:

    import 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.

    ReplyDelete

Post a Comment

Popular posts from this blog

Advent of Code - Day 6, 2024: BFS and FSM

Advent of Code - Day 7, 2024: Backtracking and Eval

Golang vs. C#: performance characteristics (simple case study)