题解 | #字符串的排列#

package main
import "strings"
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param str string字符串 
 * @return string字符串一维数组
*/
var res []string
var chars []string
func Permutation( str string ) []string {
    // write code here
    chars = strings.Split(str, "")
	dfs(0)
	return res
}


func dfs(start int) {
	//遍历到结尾
	if start == len(chars)-1 {
		//将切片转为string
		res = append(res, strings.Join(chars, ""))
		return
	}
	existMap := make(map[string]int, 0)
	for i := start; i < len(chars); i++ {
		//同一层递归中，存在相同的字符，跳过
		if _, ok := existMap[chars[i]]; ok {
			continue
		}
		//记录字符
		existMap[chars[i]] = 1
		//交换字符
		swap(i, start)
		//递归
		dfs(start + 1)
		//恢复交换的字符
		swap(start, i)
	}
}

func swap(i, j int) {
	tmp := chars[i]
	chars[i] = chars[j]
	chars[j] = tmp
}