Remove Invalid Parentheses


#1

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 ).

Example 1:

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

Example 2:

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

Example 3:

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

#2

The below algorithm uses a DFS approach to efficiently delete the invalid parentheses and add the result string to a list.

func removeInvalidParentheses(s string) []string {
    result := make([]string, 0)
    remove(s, &result,0, 0, []byte{'(', ')'})
    return result
}

func remove(s string, result *[]string,start, lastRemovedIdx int, par []byte){
    fmt.Println(s)
    for stack,i:= 0, start;i<len(s);i++{
        if s[i]==par[0] { stack++}
        if s[i]==par[1]{ stack-- }
        if stack>=0{continue}
        for j:=lastRemovedIdx;j<=i;j++{
            if(s[j]==par[1] && (j==lastRemovedIdx || s[j-1]!=par[1])){
                remove(s[:j]+s[j+1:], result, i, j, par)
            }
        }
        return
    }
    s = reverse(s)
    if par[0]=='('{
        remove(s, result, 0, 0, []byte{')', '('})
    } else {
        *result = append(*result, s)
    }
}


func reverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}