This is a Leetcode problem -
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note -
The input string may contain letters other than the parentheses
(
and)
.
Here is my solution to this challenge -
def remove_invalid_parentheses(s): removed = 0 results = {s} count = {"(": 0, ")": 0} for i, c in enumerate(s): if c == ")" and count["("] == count[")"]: new_results = set() while results: result = results.pop() for j in range(i - removed + 1): if result[j] == ")": new_results.add(result[:j] + result[j + 1:]) results = new_results removed += 1 else: if c in count: count[c] += 1 count = {"(": 0, ")": 0} i = len(s) ll = len(s) - removed for ii in range(ll - 1, -1, -1): i-=1 c = s[i] if c == "(" and count["("] == count[")"]: new_results = set() while results: result = results.pop() for j in range(ii, ll): if result[j] == "(": new_results.add(result[:j] + result[j + 1:]) results = new_results ll -= 1 else: if c in count: count[c] += 1 return list(results)
Explanation -
- Scan from left to right, make sure
count["("] >= count[")"]
. - Then scan from right to left, make sure
count["("] <= count[")"]
.
Here are some inputs/outputs -
print(remove_invalid_parentheses("()())()")) >>> ["()()()", "(())()"] print(remove_invalid_parentheses("(a)())()")) >>> ["(a)()()", "(a())()"] print(remove_invalid_parentheses(")(")) >>> [""]
Here are the times taken for each output -
%timeit remove_invalid_parentheses("()())()")
6.54 µs ± 176 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit remove_invalid_parentheses("(a)())()")
8.43 µs ± 1.29 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit remove_invalid_parentheses(")(")
3.69 µs ± 67.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
So, I would like to know whether I could make this program shorter and more efficient.
Any help would be highly appreciated.