Jianbo Dai's

jz038.字符串的排列

 
  • Jun 28, 2020

题目链接

这个题的思路很简单，求排列组合，我们可以将问题分解成小的问题。比如，我们把一个字符串堪称由两部分组成：第一部分是它的第一个字符；第二部分是后面的所有字符。我们求整个字符串的排列，可以看成两步：第一步求所有可能出现在第一个位置的字符，即把所有第一个字符和后面的所有字符交换；第二步固定第一个字符，求后面所有字符的排列。求后面所有字符的排列的时候，我们仍把后面的所有字符分成两部分：后面字符中的第一个字符，以及这个字符之后的所有字符。这个思路就是典型的递归思路。这个算法的时间复杂度是O（N!），空间复杂度是O（N^2）。

class Solution:
    def permutation(self, s: str) -> List[str]:
        c, res = list(s), []
        def recursion(x):
            if x == len(s) - 1:
                res.append(''.join(c))
                return
            dic = set()
            for i in range(x, len(c)):
                if c[i] in dic:
                    continue
                dic.add(c[i])
                c[i], c[x] = c[x], c[i]
                recursion(x+1)
                c[i], c[x] = c[x], c[i]
        recursion(0)
        return res
Search