LeetCode 301. Remove Invalid Parentheses

Description

https://leetcode.com/problems/remove-invalid-parentheses/

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return all the possible results. You may return the answer in any order.

Example 1:

Input: s = "()())()"
Output: ["(())()","()()()"]

Example 2:

Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]

Example 3:

Input: s = ")("
Output: [""]

Constraints:

  • 1 <= s.length <= 25
  • s consists of lowercase English letters and parentheses '(' and ')'.
  • There will be at most 20 parentheses in s.

Explanation

Use depth-first search to find valid strings.

Python Solution

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        results = []
        
        left, right = self.left_right_count(s)
        
        self.dfs_helper(s, left, right, 0, results)
        
        return results
    
    
    def left_right_count(self, s):
        left = 0
        right = 0
        
        for c in s:
            if c == '(':
                left += 1
            elif c == ')':
                if left > 0:
                    left -= 1
                else:
                    right += 1
                    
        return left, right
    
    
    def is_valid(self, s):
        left, right = self.left_right_count(s)
        return left == 0 and right == 0
    
    def dfs_helper(self, s, left, right, start, results):
        if left == 0 and right == 0:
            if self.is_valid(s):
                results.append(s)
                return
        
        for i in range(start, len(s)):
            if i > start and s[i] == s[i - 1]:
                continue
                
            if s[i] == '(':
                self.dfs_helper(s[:i] + s[i + 1:], left - 1, right, i, results)
            elif s[i] == ')':
                self.dfs_helper(s[:i] + s[i + 1:], left, right - 1, i, results)
                 
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.