Sponsored
Sponsored
This approach uses a BFS technique. The idea is to start with the original string and try to remove each parenthesis at each level, generating a new state each time. We are looking for the shortest valid string, hence the BFS approach ensures that we explore the minimum removal solution first.
The critical parts of the approach are:
Time Complexity: O(2^n). For each character in the string, there are two choices: include it or not, hence exponential complexity. However, pruning the search space often reduces this in practical scenarios.
Space Complexity: O(n). Space is used to store the queue and the set of visited states.
1from collections import deque
2
3def removeInvalidParentheses(s):
4 def isValid(string):
5 balance = 0
6 for char in string:
7 if char == '(': balance += 1
8 if char == ')': balance -= 1
9 if balance < 0: return False
10 return balance == 0
11
12 queue = deque([s])
13 visited = set([s])
14 found = False
15 valid_expressions = []
16
17 while queue:
18 expression = queue.popleft()
19
20 if isValid(expression):
21 found = True
22 valid_expressions.append(expression)
23
24 if found:
25 continue
26
27 for i in range(len(expression)):
28 if expression[i] not in ('(', ')'):
29 continue
30 next_expression = expression[:i] + expression[i+1:]
31 if next_expression not in visited:
32 visited.add(next_expression)
33 queue.append(next_expression)
34
35 return valid_expressionsThis Python function uses a queue to explore each possible state of the string. For each invalid state, we remove one parenthesis at each position and check the new state. A visited set is used to avoid processing the same string multiple times, ensuring more efficient performance.
DFS with backtracking is a common technique in situations where all combinations must be explored. In this problem, we explore each possible configuration and backtrack when we identify that no valid state can follow the current configuration.
The primary characteristics of this approach are:
Time Complexity: O(2^n). Each character has two choices: include or exclude. Backtracking and pruning noticeably reduce practical complexity.
Space Complexity: O(n). Stack space utilized during recursion along with sets to store unique valid combinations.
1function removeInvalidParentheses(s) {
This JavaScript function utilizes DFS and backtracking to explore each state's depth, leveraging a pruning strategy to skip duplicate configurations and strings that exceed the minimum removal already encountered. The use of a Set avoids duplicates in the final result.