LeetCode: 301. Remove Invalid Parentheses

LeetCode: 301. Remove Invalid Parentheses

题目描述

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: [""]

解题思路 —— 深度优先搜索

根据要求深度优先搜索

AC 代码

func removeInvalidParenthesesRef(s string, stk []byte, cur []byte, ans *[]string)  {
    if len(s) == 0 {
        if len(stk) != 0 { return }
        
        if len(*ans) == 0 || len((*ans)[0]) == len(cur) {
            *ans = append(*ans, string(cur)) 
        } else if len((*ans)[0]) < len(cur) {
            (*ans)[0] = string(cur)
            (*ans) = (*ans)[0:1]
        }
        
        return
    }
    
    cur = append(cur, s[0])
    if s[0] != '(' && s[0] != ')' {
        removeInvalidParenthesesRef(s[1:], stk, cur, ans)
        return
    } else if s[0] == '(' {
        stk = append(stk, s[0])
        removeInvalidParenthesesRef(s[1:], stk, cur, ans)
        stk = stk[:len(stk)-1]
    } else if len(stk) != 0 && stk[len(stk)-1] == '(' {
        removeInvalidParenthesesRef(s[1:], stk[:len(stk)-1], cur, ans)
    }
    
    cur = cur[:len(cur)-1];
    removeInvalidParenthesesRef(s[1:], stk, cur, ans)
}

func removeDup(ans []string) []string {
    for i := 1; i < len(ans); i++{
        for j := 0; j < i; j++{
            if ans[i] == ans[j] {
                ans = append(ans[:i], ans[i+1:]...)
                i--
                break
            }
        }
    }
    
    return ans
}

func removeInvalidParentheses(s string) []string {
    var stk []byte
    var cur []byte
    var ans []string
    
    // 1. 求最长有效括号 
    removeInvalidParenthesesRef(s, stk, cur, &ans)
    
    // 2. 去除重复元素
    ans = removeDup(ans)
    
    return ans
}