寻找合法字符串

[编程题]寻找合法字符串

热度指数：2245 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个正整数n，请给出所有的包含n个'('和n个')'的字符串，使得'('和')'可以完全匹配。

例如：

'(())()'，'()()()' 都是合法的；

'())()('是不合法的。

请按照__字典序__给出所有合法的字符串。

输入描述:

输入为1个正整数

输出描述:

输出为所有合法的字符串，用英文逗号隔开

示例1

输入

输出

(()),()()

算法知识视频讲解

Python3

TS9527

DFS，注意排查非法情况

class MainActivity:

    def main(self):
        # Read the data
        n = int(input())
        # Initialization
        results = set()
        self.__generate('', n, n, results)
        # Print the result
        results = sorted(list(results))
        print(','.join(results))
    
    def __generate(self, prefix, left, right, results):
        if not right:
            if not left:
                results.add(prefix)
            return
        if left:
            self.__generate(prefix + '(', left - 1, right, results)
        if right > left:
            self.__generate(prefix + ')', left, right - 1, results)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-08-26 13:44:47 回复(0)