Problem: Given a balanced parentheses string S, compute the score of the string based on the following rule:
- ( ) has score 1
- AB has score A + B, where A and B are balanced parentheses strings.
- (A) has score 2 * A, where A is a balanced parentheses string.
Example:
Input: "()" Output: 1
Input: "(())" Output: 2
Input: "()()" Output: 2
Input: "(()(()))" Output: 6
Approach: We can use stack here. The approach is straight forward and you can understand it by just looking at the code. This approach will solve the problem in linear time (ignoring int to string and string to int conversions) but it will take extra space. Let's try to do better.
If you look at the problem closely, you will understand the result is sum of power of 2s. Let's see through examples:
- ( ) => 2 ^ 0 = 1
- ( ) ( ) => 2 ^0 + 2^0 = 2
- ( ( ) ) => 2^1 = 2
- ( ( ( ) ) ) => 2^2 = 4
- ( ( ) ) ( ( ( ) ) ) => 2^1 + 2^2 = 6
Basically inner '( )' means increment in power of 2. With this intuition just look at the implementation of approach 2 which is fairly straight forward.
Implementation in C#:
Approach 1:
public int ScoreOfParentheses(string S)
{
Stack<string> stack = new Stack<string>();
foreach (char ch in S)
{
if (ch == '(')
{
stack.Push(ch.ToString());
}
else
{
int result = 0;
while (stack.Count > 0 && stack.Peek() != "(")
{
result += int.Parse(stack.Pop());
}
stack.Pop();
if (result == 0)
{
stack.Push("1");
}
else
{
stack.Push((result * 2).ToString());
}
}
}
int answer = 0;
while (stack.Count > 0)
{
answer += int.Parse(stack.Pop());
}
return answer;
}
Approach 2:
public int ScoreOfParentheses(string S)
{
int powOfTwo = 0;
int result = 0;
for (int i = 0; i < S.Length; ++i)
{
if (S[i] == '(')
{
++powOfTwo;
}
else
{
--powOfTwo;
if (S[i - 1] == '(')
{
result += (1 << powOfTwo);
}
}
}
return result;
}
Complexity: O(n)
No comments:
Post a Comment