题解 | #字符串的排列#

递归思想

• 长度为 n 的字符串，是在其前 n - 1 个字符的所有排列的子字符串中，从前到后依此插入最后一个字符所得；

  ...

  ...

• 长度为 4 的字符串，是在其前 3 个字符的所有排列的子字符串中，从前到后依此插入最后一个字符所得；

• 长度为 3 的字符串，是在其前 2 个字符的所有排列的子字符串中，从前到后依此插入最后一个字符所得；

• 长度为 2 的字符串，是在其前 1 个字符的所有排列的子字符串中，从前到后依此插入最后一个字符所得；

例如：

• 'ab' 的所有排列为 ['ab', 'ba']

  可以视为是在 ['a'] 的 0, 1 位置分别插入'b' 所得；

• 'abc' 的所有排列为 ['cab', 'acb', 'abc', 'cba', 'bca', 'bac']

  可以视为是在 'ab' 的所有排列的字符串中 0, 1, 2 的位置，依次插入 'c' 所得，即：

  'c' 在 'ab' 所转换的列表 ['a', 'b'] 的 0, 1, 2 的位置分别插入 'c' ，再合并成字符串所得 ['cab', 'acb', 'abc'];

  'c' 在 'ba' 所转换的列表 ['b', 'a'] 的 0, 1, 2 的位置分别插入 'c' ，再合并成字符串所得 ['cba', 'bca', 'bac'];

  再将两个列表合并为一个。

依此类推……最后记得去重。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @return string字符串一维数组
#
class Solution:
    def Permutation(self , s: str) -> List[str]:
        # write code here
        if len(s) <= 1:
            return s
        out = []
        fix_s = s[-1]
        dg = self.Permutation(s[:-1])
        print(dg)
        for each in dg:
            temp_list_str = self.insert(each, fix_s)
            out.extend(temp_list_str)
        
        return list(set(out))
            
    def insert(self, s, x):
        out = []
        sl = list(s)
        for i in range(len(s) + 1):
            new_s = sl.copy()
            new_s.insert(i, x)
            out.append(''.join(new_s))

        return out