题解 | #字符串的排列#

package main

import (
	"sort"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str string字符串
 * @return string字符串一维数组
 */
func Permutation(str string) []string {
	var result []string
	s := []rune(str)
	sort.Slice(s, func(i, j int) bool { return s[i] < s[j] }) // 对字符进行排序
	permuteUnique(s, 0, &result)
	return result
}

func permuteUnique(s []rune, start int, result *[]string) {
	if start == len(s) {
		*result = append(*result, string(s))
		return
	}
	used := make(map[rune]bool) // 用于记录当前递归层级已选择过的字符
	for i := start; i < len(s); i++ {
		if used[s[i]] || (i > start && s[i] == s[i-1]) {
			continue // 跳过已使用的字符或相邻且相同的字符
		}
		used[s[i]] = true
		s[start], s[i] = s[i], s[start]
		permuteUnique(s, start+1, result)
		s[start], s[i] = s[i], s[start]
	}
}