Posts tagged as “parentheses”

花花酱 LeetCode 2267. Check if There Is a Valid Parentheses String Path

By zxi on May 10, 2022

A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:

It is ().
It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
It can be written as (A), where A is a valid parentheses string.

You are given an m x n matrix of parentheses grid. A valid parentheses string path in the grid is a path satisfying all of the following conditions:

The path starts from the upper left cell (0, 0).
The path ends at the bottom-right cell (m - 1, n - 1).
The path only ever moves down or right.
The resulting parentheses string formed by the path is valid.

Return true if there exists a valid parentheses string path in the grid. Otherwise, return false.

Example 1:

Input: grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
Output: true
Explanation: The above diagram shows two possible paths that form valid parentheses strings.
The first path shown results in the valid parentheses string "()(())".
The second path shown results in the valid parentheses string "((()))".
Note that there may be other valid parentheses string paths.

Example 2:

Input: grid = [[")",")"],["(","("]]
Output: false
Explanation: The two possible paths form the parentheses strings "))(" and ")((". Since neither of them are valid parentheses strings, we return false.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j] is either '(' or ')'.

Solution: DP

Let dp(i, j, b) denote whether there is a path from (i,j) to (m-1, n-1) given b open parentheses.
if we are at (m – 1, n – 1) and b == 0 then we found a valid path.
dp(i, j, b) = dp(i + 1, j, b’) or dp(i, j + 1, b’) where b’ = b + 1 if grid[i][j] == ‘(‘ else -1

Time complexity: O(m*n*(m + n))
Space complexity: O(m*n*(m + n))

Python3

# Author: Huahua

class Solution:

def hasValidPath(self, grid: List[List[str]]) -> bool:

m, n = len(grid), len(grid[0])

@cache

def dp(i: int, j: int, b: int) -> bool:

if b < 0 or i == m or j == n: return False

b += 1 if grid[i][j] == '(' else -1

if i == m - 1 and j == n - 1 and b == 0: return True

return dp(i + 1, j, b) or dp(i, j + 1, b)

return dp(0, 0, 0)

花花酱 LeetCode 2232. Minimize Result by Adding Parentheses to Expression

By zxi on April 9, 2022

You are given a 0-indexed string expression of the form "<num1>+<num2>" where <num1> and <num2> represent positive integers.

Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of '+' and the right parenthesis must be added to the right of '+'.

Return expression after adding a pair of parentheses such that expression evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.

The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Example 1:

Input: expression = "247+38"
Output: "2(47+38)"
Explanation: The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the '+'.
It can be shown that 170 is the smallest possible value.

Example 2:

Input: expression = "12+34"
Output: "1(2+3)4"
Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.

Example 3:

Input: expression = "999+999"
Output: "(999+999)"
Explanation: The expression evaluates to 999 + 999 = 1998.

Constraints:

3 <= expression.length <= 10
expression consists of digits from '1' to '9' and '+'.
expression starts and ends with digits.
expression contains exactly one '+'.
The original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Solution: Brute Force

Try all possible positions to add parentheses and evaluate the new expression.

Time complexity: O(n²)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string minimizeResult(string expression) {

const int n = expression.size();

auto p = expression.find('+');

int best = INT_MAX;

string ans;

for (int l = 0; l < p; ++l)

for (int r = p + 2; r < n + 1; ++r) {

const int m1 = l ? stoi(expression.substr(0, l)) : 1;

const int m2 = (r < n) ? stoi(expression.substr(r)) : 1;

const int n1 = stoi(expression.substr(l, p));

const int n2 = stoi(expression.substr(p + 1, r - p - 1));

const int cur = m1 * (n1 + n2) * m2;

if (cur < best) {

best = cur;

ans = expression;

ans.insert(l, "(");

ans.insert(r + 1, ")");

}

return ans;

}

};

花花酱 LeetCode 1614. Maximum Nesting Depth of the Parentheses

By zxi on October 10, 2020

A string is a valid parentheses string (denoted VPS) if it meets one of the following:

It is an empty string "", or a single character not equal to "(" or ")",
It can be written as AB (A concatenated with B), where A and B are VPS‘s, or
It can be written as (A), where A is a VPS.

We can similarly define the nesting depth depth(S) of any VPS S as follows:

depth("") = 0
depth(A + B) = max(depth(A), depth(B)), where A and B are VPS‘s
depth("(" + A + ")") = 1 + depth(A), where A is a VPS.

For example, "", "()()", and "()(()())" are VPS‘s (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS‘s.

Given a VPS represented as string s, return the nesting depth of s.

Example 1:

Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
Explanation: Digit 8 is inside of 3 nested parentheses in the string.

Example 2:

Input: s = "(1)+((2))+(((3)))"
Output: 3

Example 3:

Input: s = "1+(2*3)/(2-1)"
Output: 1

Example 4:

Input: s = "1"
Output: 0

Constraints:

1 <= s.length <= 100
s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
It is guaranteed that parentheses expression s is a VPS.

Solution: Stack

We only need to deal with ‘(‘ and ‘)’

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxDepth(string s) {

int ans = 0;

int d = 0;

for (char c : s) {

if (c == '(') ans = max(ans, ++d);

else if (c == ')') --d;

}

return ans;

}

};

花花酱 LeetCode 1541. Minimum Insertions to Balance a Parentheses String

By zxi on August 9, 2020

Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:

Any left parenthesis '(' must have a corresponding two consecutive right parenthesis '))'.
Left parenthesis '(' must go before the corresponding two consecutive right parenthesis '))'.

For example, "())", "())(())))" and "(())())))" are balanced, ")()", "()))" and "(()))" are not balanced.

You can insert the characters ‘(‘ and ‘)’ at any position of the string to balance it if needed.

Return the minimum number of insertions needed to make s balanced.

Example 1:

Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to to add one more ')' at the end of the string to be "(())))" which is balanced.

Example 2:

Input: s = "())"
Output: 0
Explanation: The string is already balanced.

Example 3:

Input: s = "))())("
Output: 3
Explanation: Add '(' to match the first '))', Add '))' to match the last '('.

Example 4:

Input: s = "(((((("
Output: 12
Explanation: Add 12 ')' to balance the string.

Example 5:

Input: s = ")))))))"
Output: 5
Explanation: Add 4 '(' at the beginning of the string and one ')' at the end. The string becomes "(((())))))))".

Constraints:

1 <= s.length <= 10^5
s consists of '(' and ')' only.

Solution: Counting

Count how many close parentheses we need.

if s[i] is ‘)’, we decrease the counter.
1. if counter becomes negative, means we need to insert ‘(‘
  1. increase ans by 1, increase the counter by 2, we need one more ‘)’
  2. ‘)’ -> ‘()’
if s[i] is ‘(‘
1. if we have an odd counter, means there is a unbalanced ‘)’ e.g. ‘(()(‘, counter is 3
  1. need to insert ‘)’, decrease counter, increase ans
  2. ‘(()(‘ -> ‘(~~())~~(‘, counter = 2
2. increase counter by 2, each ‘(‘ needs two ‘)’s. ‘(~~())~~(‘ -> counter = 4
Once done, if counter is greater than zero, we need insert that much ‘)s’
1. counter = 5, ‘((()’ -> ‘((())))))’

Time complexity: O(n)
Space complexity: O(1)

C++

class Solution {

public:

int minInsertions(string s) {

int ans = 0;

int close = 0; // # of ')' needed.

for (char c : s) {

if (c == ')') {

if (--close < 0) {

// need to insert one '('

// ')' -> '()'

++ans;

close += 2;

}

} else {

if (close & 1) {

// need to insert one ')'

// case '(()(' -> '(())('

--close;

++ans;

}

close += 2; // need two ')'s

}

return ans + close;

}

};

花花酱 1249. Minimum Remove to Make Valid Parentheses

By zxi on November 9, 2019

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Example 4:

Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"

Constraints:

1 <= s.length <= 10^5
s[i] is one of '(' , ')' and lowercase English letters.

Solution: Couting

Count how many “(” are open and how many “)” left.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string minRemoveToMakeValid(string s) {

int close = count(begin(s), end(s), ')');

int open = 0;

string ans;

for (char c : s) {

if (c == '(') {

if (open == close) continue;

++open;

} else if (c == ')') {

--close;

if (open == 0) continue;

--open;

}

ans += c;

}

return ans;

}

};