題目

給你一個由 '('、')' 和小寫字母組成的字串 s。

請返回任意一個合法字串。

有效「括號字串」應當符合以下 任意一條 要求：

空字串或只包含小寫字母的字串

可以被寫作 AB（A 連線 B）的字串，其中 A 和 B 都是有效「括號字串」

可以被寫作 (A) 的字串，其中 A 是一個有效的「括號字串」

示例 1：輸入：s = "lee(t(c)o)de)" 輸出："lee(t(c)o)de"

解釋："lee(t(co)de)" , "lee(t(c)ode)" 也是一個可行答案。

示例 2：輸入：s = "a)b(c)d" 輸出："ab(c)d"

示例 3：輸入：s = "))((" 輸出：""

解釋：空字串也是有效的

示例 4：輸入：s = "(a(b(c)d)" 輸出："a(b(c)d)"

提示：1 <= s.length <= 10^5

s[i] 可能是 '('、')' 或英文小寫字母

解題思路分析

1、遍歷；時間複雜度O(n)，空間複雜度O(n)

func minRemoveToMakeValid(s string) string {	arr := []byte(s)	sum := 0	for i := 0; i < len(arr); i++ {		if arr[i] == '(' {			sum++		} else if arr[i] == ')' {			sum--			if sum < 0 {				arr[i] = ' '				sum = 0			}		}	}	sum = 0	for i := len(arr) - 1; i >= 0; i-- {		if arr[i] == ')' {			sum++		} else if arr[i] == '(' {			sum--			if sum < 0 {				arr[i] = ' '				sum = 0			}		}	}	return strings.ReplaceAll(string(arr), " ", "")}

2、棧輔助；時間複雜度O(n)，空間複雜度O(n)

func minRemoveToMakeValid(s string) string {	arr := []byte(s)	stack := make([]int, 0)	for i := 0; i < len(arr); i++ {		if arr[i] == '(' {			stack = append(stack, i)		} else if arr[i] == ')' {			if len(stack) == 0 {				arr[i] = ' '			} else {				stack = stack[:len(stack)-1]			}		}	}	for i := 0; i < len(stack); i++ {		arr[stack[i]] = ' '	}	return strings.ReplaceAll(string(arr), " ", "")}

總結

Medium題目，可以遍歷2遍分別消除')'和'('，也可以藉助棧消除不滿足條件的'('和')'