leetcode 22-Generate Parentheses

按照顺序打印括号。用 DFS 搜索

package main

import "fmt"

func isValid(s string) bool {
    stack := make([]string, len(s))
    index := 0
    for _, v := range s {
        if string(v) == "(" {
            index++
            stack[index] = "("
        } else {
            index--
            if index < 0 {
                return false
            }
        }
    }
    return true
}

func dfs(left int, right int, s string, result *[]string) {
    if left > right {
        return
    }
    if left > 0 {
        dfs(left-1, right, s+"(", result)
    }
    if right > 0 {
        dfs(left, right-1, s+")", result)
    }

    if left == 0 && right == 0 {
        *result = append(*result, s)
    }
}

func generateParenthesis(n int) []string {
    all := make([]string, 0)
    result := make([]string, 0)
    dfs(n-1, n, "(", &all)
    for _, r := range all {
        if isValid(r) == true {
            result = append(result, r)
        }
    }
    return result
}

func main() {
    fmt.Println(generateParenthesis(3))
}

o0w0o / ARTS

leetcode 22-Generate Parentheses #98