leetcod generate parentheses

[hyponet]

https://leetcode.com/problems/generate-parentheses 搜索加括号匹配

[hyponet]

DFS

package main

import "fmt"

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

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

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

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

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

[hyponet]

BFS

package main

import "fmt"

type Case struct {
    pattern string
    left    int
    right   int
}

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

func generateParenthesis(n int) []string {
    queue := make([]Case, 0)
    queue = append(queue, Case{
        pattern: "(",
        left:    n - 1,
        right:   n,
    })
    allCase := make([]string, 0)
    for len(queue) > 0 {
        now := queue[0]
        queue = queue[1:]

        if now.left > 0 {
            queue = append(queue, Case{
                pattern: now.pattern + "(",
                left:    now.left - 1,
                right:   now.right,
            })
        }

        if now.right > 0 {
            queue = append(queue, Case{
                pattern: now.pattern + ")",
                left:    now.left,
                right:   now.right - 1,
            })
        }

        if now.right == 0 && now.right == now.left {
            allCase = append(allCase, now.pattern)
        }
    }
    ans := make([]string, 0)
    for _, c := range allCase {
        if isValid(c) {
            ans = append(ans, c)
        }
    }
    return ans
}

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