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.
1#include <iostream>
2#include <queue>
3#include <unordered_set>
4#include <vector>
5using namespace std;
6
7bool isValid(const string &s) {
8 int balance = 0;
9 for (char c : s) {
10 if (c == '(') balance++;
11 if (c == ')') balance--;
12 if (balance < 0) return false;
13 }
14 return balance == 0;
15}
16
17vector<string> removeInvalidParentheses(string s) {
18 unordered_set<string> visited;
19 queue<string> q;
20 vector<string> result;
21 q.push(s);
22 visited.insert(s);
23 bool found = false;
24
25 while (!q.empty()) {
26 string str = q.front(); q.pop();
27
28 if (isValid(str)) {
29 found = true;
30 result.push_back(str);
31 }
32
33 if (found) continue;
34
35 for (size_t i = 0; i < str.length(); ++i) {
36 if (str[i] != '(' && str[i] != ')') continue;
37 string next = str.substr(0, i) + str.substr(i + 1);
38 if (!visited.count(next)) {
39 visited.insert(next);
40 q.push(next);
41 }
42 }
43 }
44 return result;
45}The C++ implementation follows the BFS principle similarly. It checks each level for validity and only proceeds when a valid configuration can't be found at the current level. This stops further unnecessary string generation, ensuring the minimum removal state is achieved.
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.