字符串的排列

题目表述

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例

输入：s = "abc"

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

限制

1 <= s 的长度 <= 8

解法一：递归实现

代码实现

from typing import List


class Solution:
    def permutation(self, s: str) -> List[str]:
        ans = set()

        def recur(s: str, prev: str = ""):
            if len(s) == 1:
                ans.add(prev + s)
            for i, v in enumerate(s):
                recur(s[:i] + s[i + 1 :], prev + v)

        recur(s)
        return list(ans)


if __name__ == "__main__":
    s = "abc"
    ans = Solution().permutation(s)
    print(ans)

package leetcode

func permutation(s string) []string {
	ans := map[string]bool{}
	var recur func(subStr, prefix string)
	recur = func(subStr, prefix string) {
		if len(subStr) == 1 {
			ans[prefix+string(subStr[0])] = true
			return
		}
		for i, v := range subStr {
			recur(subStr[:i]+subStr[1+i:], prefix+string(v))
		}
	}
	recur(s, "")
	res := make([]string, len(ans))
	i := 0
	for key := range ans {
		res[i] = key
		i += 1
	}
	return res
}