【Leetcode】:22. Generate Parentheses 问题 in Go语言

u013564276 · · 1270 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"


解题思路:这道题和N-Queen问题非常类似,几乎是一样的解题模式。

首先需要明白,怎么放置括号是合法的,假设n=5的情况,已经合法的放置了4个括号,那么怎么判断下一个放什么括号合法呢?

放左括号:如果之前放置的左括号数>=n,那么一定不合法

放右括号:如果之前放置的左括号数<=之前放置的右括号数,那么一定不合法

func generateParenthesis(n int) []string {
    str := make([]string,0)
    position := make([]int, n * 2) //第i个小标表示位置i上是左括号还是右括号,0表示左括号1表示右括号
    placeParentheses(position, &str, 0, n)
    return str
}

func placeParentheses(position []int, str *[]string, i, n int) {
        if i == 2 * n { //当所有的括号都放完了
            var s string
            for _, v := range position {
                if v == 0 {
                    s += "("
                } else {
                    s += ")"
                }
            }
            *str = append(*str, s)
            return
        }
        if isValid(position, i, 0, n) { //放左括号是否合法
            position[i] = 0
            placeParentheses(position, str, i + 1, n)
        }
        if isValid(position, i, 1, n) { //放右括号是否合法
            position[i] = 1
            placeParentheses(position, str, i + 1, n)
        }
}

func isValid(position []int, cur int, LR int, n int) bool {
    var num_left, num_right int
    for i := 0; i < cur; i++ {
        if position[i] == 0 {
            num_left++
        } else {
            num_right++
        }
    }
    if LR == 0 { //如果当前放入的是左括号
        if num_left >= n {
            return false
        }
    } else {   //如果当前放入的是右括号
        if num_left <= num_right {
            return false
        }
    }
    return true
}



有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:u013564276

查看原文:【Leetcode】:22. Generate Parentheses 问题 in Go语言

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

1270 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传