301.md

title	date
301. 删除无效的括号	2018-12-02T09:41:00.000Z

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

使用语言: Golang

func check (s string) (int, int) {
    left := 0
    right := 0
    for _,bracket := range s {
        bracketStr := string(bracket)
        if bracketStr == "(" {
            left++
        } else if bracketStr == ")" {
            if left > 0 {
                left--
            } else {
                right++
            }
        }
    }
    return left, right
}

func removeInvalidParenthesesHelper(s string, i int, pair int, left int, right int, solution string, m map[string]int) {
    if i >= len(s) {
        // 完全匹配
        if pair == 0 && left == 0 && right == 0 {
            m[solution] = 1
        }
        return
    }
    char := string(s[i])
    if char == "(" {
        if left > 0 {
            // 计算一遍将其删去的情况
            removeInvalidParenthesesHelper(s, i + 1, pair, left - 1, right, solution, m)
        }
        // 计算一遍不将其删去的情况
        removeInvalidParenthesesHelper(s, i + 1, pair + 1, left, right, solution + char, m)
    } else if char == ")" {
        if right > 0 {
            removeInvalidParenthesesHelper(s, i + 1, pair, left, right - 1, solution, m)
        }
        // 防止出现无法配对的情况
        if pair > 0 {
            removeInvalidParenthesesHelper(s, i + 1, pair - 1, left, right, solution + char, m)
        }
    } else {
        removeInvalidParenthesesHelper(s, i + 1, pair, left, right, solution + char, m)
    }
}

func removeInvalidParentheses(s string) []string {
    cLeft, cRight := check(s)
    m := make(map[string]int)
    removeInvalidParenthesesHelper(s, 0, 0, cLeft, cRight, "", m)
    keys := []string{}
    for key := range m {
        keys = append(keys, key)
    }
    return keys
}

解题思路

解答这道题的思路是要找到这个问题的最小子问题。 题目要求我们用最小的代价删除无效的括号，并输出所有可能的结果。我寻找子问题的过程如下：

1. 怎么确定最小代价？一个 "(" 对应一个 ")" ，那么没有对应的，就是多余的。有几个多余我们就要删掉几个
2. 怎么找到所有可能结果？ a. 先确定结果应当满足的条件：每个 "(" 都有一个 ")" 与之对应，删掉的字符与第一步确定的最小代价一致 b. 如何找到结果集中的任意一个结果：遍历字符串，按照第一步得到的最小代价，逐个尝试，直到其满足条件