程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode Generate Parentheses

LeetCode Generate Parentheses

編輯:C++入門知識

LeetCode Generate Parentheses


LeetCode解題之Generate Parentheses


原題

羅列出n組括號的所有合法的排列組合。

注意點:

只有一種括號形式”()”

例子:

輸入: n = 3
輸出: [‘((()))’, ‘(()())’, ‘(())()’, ‘()(())’, ‘()()()’]

解題思路

我們先來討論一下什麼樣的排列是不合法的,由於只有一種類型的括號,所以我們只要時刻保持字符串中的左括號不少於右括號即可。例如:字符串”)*“上來就右括號數目比左括號多,它就是不合法的,沒有左括號來與第一個右括號組合。在進行遞歸的時候注意優先添加左括號,在現有右括號少於左括號的情況下,可以添加右括號。遞歸的結束條件是所有的括號都已加入字符串中。

AC源碼

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        result = []
        self.generate(n, n, "", result)
        return result

    def generate(self, left, right, str, result):
        if left == 0 and right == 0:
            result.append(str)
            return
        if left > 0:
            self.generate(left - 1, right, str + "(", result)
        if right > left:
            self.generate(left, right - 1, str + ")", result)


if __name__ == "__main__":
    assert (Solution().generateParenthesis(3)) == ['((()))', '(()())', '(())()', '()(())', '()()()']

歡迎查看我的Github來獲得相關源碼。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved