leetcode-go/leetcode/medium/678.valid-parenthesis-string.go

func checkValidString(s string) bool {
	set := make(map[int]bool) // Records ALL POSSIBLE VALID num of lb - rb
	set[0] = true
	for _, r := range s {
		nset := make(map[int]bool)
		switch r {
		case '(':
			for k := range set {
				nset[k+1] = true
			}
		case ')':
			for k := range set {
				if 0 < k {
					nset[k-1] = true
				}
			}
		default:
			for k := range set {
				nset[k+1] = true
				nset[k] = true
				if 0 < k {
					nset[k-1] = true
				}
			}
		}
		set = nset
	}
	return set[0] // Check if 0 is possible
}