题解 | #牛牛的字符串排列#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @param k int整型 
# @return string字符串一维数组
#
class Solution:
    def getPermutation(self , s: str, k: int) -> List[str]:
        # write code here
        # s <= 8  8! = 4*10**4
        # 字典序排列，可以到k就中断
        ans = set()
        def getP(cur, left):
            # BC
            if len(ans) == k:
                return # 已经搜集到足够的串
            
            if not left:
                ans.add(''.join(cur))
                return
            
            # 字典序
            left = sorted(left)
            # 首字母选择排序
            for i in range(len(left)):
                cur_L = left[i]
                getP(cur + [cur_L], left[:i] + left[i+1:])

            
        getP([], list(s))

        return sorted(list(ans))

因为需要记录路径，并且只需要字典序前k个，所以考虑使用DFS，一旦满足k个就不需要继续了。

每次将排序后的第一个char加入现有的字符串，然后遍历，根据递归的性质，这样保证我们每次都加入在字典序前面的字符，从而满足题目要求的字典序排列的要求。