題目

給定一個只包含三種字元的字串：（ ，） 和 *，寫一個函式來檢驗這個字串是否為有效字串。

有效字串具有如下規則：

任何左括號 ( 必須有相應的右括號 )。

任何右括號 ) 必須有相應的左括號 ( 。

左括號 ( 必須在對應的右括號之前 )。

* 可以被視為單個右括號 ) ，或單個左括號 ( ，或一個空字串。

一個空字串也被視為有效字串。

示例 1:輸入: "()" 輸出: True

示例 2:輸入: "(*)" 輸出: True

示例 3:輸入: "(*))" 輸出: True

注意:字串大小將在 [1，100] 範圍內。

解題思路分析

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

func checkValidString(s string) bool {	// 第1次把星號當左括號看	left, right := 0, 0	for i := 0; i < len(s); i++ {		if s[i] == ')' {			right++		} else {			left++		}		if right > left {			return false		}	}	// 第2次把星號當右括號看	left, right = 0, 0	for i := len(s) - 1; i >= 0; i-- {		if s[i] == '(' {			left++		} else {			right++		}		if left > right {			return false		}	}	return true}

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

func checkValidString(s string) bool {	stackL := make([]int, 0)	stackS := make([]int, 0)	for i := 0; i < len(s); i++ {		if s[i] == '(' {			stackL = append(stackL, i)		} else if s[i] == '*' {			stackS = append(stackS, i)		} else {			if len(stackL) > 0 {				stackL = stackL[:len(stackL)-1]			} else if len(stackS) > 0 {				stackS = stackS[:len(stackS)-1]			} else {				return false			}		}	}	if len(stackL) > len(stackS) {		return false	}	for len(stackL) > 0 && len(stackS) > 0 {		a, b := stackL[len(stackL)-1], stackS[len(stackS)-1]		if a > b {			return false		}		stackL = stackL[:len(stackL)-1]		stackS = stackS[:len(stackS)-1]	}	if len(stackL) == 0 {		return true	}	return false}

3、遞迴；時間複雜度O(n!)，空間複雜度O(n)

func checkValidString(s string) bool {	return dfs(s, 0, 0)}func dfs(s string, index, count int) bool {	if count < 0 {		return false	}	for i := index; i < len(s); i++ {		if s[i] == '(' {			count++		} else if s[i] == ')' {			if count == 0 {				return false			}			count--		} else if s[i] == '*' {			return dfs(s, i+1, count+1) || dfs(s, i+1, count-1) || dfs(s, i+1, count)		}	}	return count == 0}

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

func checkValidString(s string) bool {	maxLeft, minLeft := 0, 0 // 可以有最多left和最少left的數量	for i := 0; i < len(s); i++ {		if s[i] == '(' {			maxLeft++			minLeft++		} else if s[i] == '*' {			maxLeft++        // *當(用			if minLeft > 0 { // *當)用				minLeft--			}		} else if s[i] == ')' {			maxLeft--			if maxLeft < 0 {				return false			}			if minLeft > 0 {				minLeft--			}		}	}	return minLeft == 0}

總結

Medium題目，括號系列問題，藉助棧的思路解決