LeetCode-求字符串全排列

发布于 2021-06-26 LeetCode 算法

¶ LeetCode 算法设计

¶ 求字符串全排列

输入一个字符串，输出该字符串的全排列。

示例 1:

1
2
3

输入：'abc’

输出：['abc', 'acb', 'bac', 'bca', 'cab', 'cba' ]

示例 2:

1
2
3

输入：''

输出：[]

¶ 算法思想

第一步是确定第一个位置的字符，就是第一个位置与后边的所有字符进行交换。
第二步，就是对除了第一个位置的后边所有位置的字符进行相同处理；直至剩下一个字符，打印；

递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串，如果有重复的，然后对结果使用set去重就可以了.

def strPermutation(self, string: str) -> list:
        res = []
        def backtrack(string, tmp):
            if not string:
                res.append(tmp)
                return
            for i in range(len(string)):
                backtrack(string[:i] + string[i+1:], tmp + string[i])

        if string == "":
            return []
        else:
            backtrack(string, "")
        return res

上一篇: ElasticSearch-CRUD 下一篇: 列表生成式

保持清醒，不断思考。

Mike lucis

¶ LeetCode 算法设计

¶ 求字符串全排列

¶ 算法思想