题解 | #字符串的排列#

package main

import (
	"sort"
    "strings"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str string字符串
 * @return string字符串一维数组
 */
func Permutation(str string) []string {
	// write code here
	if str == "" {
		return nil
	}
	var res []string
	ans := make([]string, 0)
	n := 0
	temp := ""
	for _, v := range str {
		res = append(res, string(v))
		n++
	}

	m := make([]bool, n)

	sort.Strings(res)

	recursion(res, &ans, m, n, temp)

	return ans

	//    strList := make([]string, 0, len(str))
	//     for _, v := range []byte(str) {
	//         strList = append(strList, string(v))
	//     }
	//     sort.Strings(strList)

	//     result := []string{}
	//     dfs(strList, 0, &result)

	//     return result
}

func recursion(res []string, ans *[]string, m []bool, n int, temp string) {
	if len(temp) == n {
		*ans = append(*ans, temp)
	}

	for i := 0; i < n; i++ {
		if m[i] {
			continue
		} else if i != 0 && res[i] == res[i-1] && !m[i-1] {
			continue
		}
		m[i] = true
		temp = temp + res[i]
		recursion(res, ans, m, n, temp)
		m[i] = false
		temp = temp[:len(temp)-1]
	}
}

func dfs(strs []string, index int, result *[]string) {
	// 排列到最后一位，无需再处理，直接生成字符序列
	if index == len(strs)-1 {
		newStr := strings.Join(strs, "")
		*result = append(*result, newStr)
		return
	}

	for i := index; i < len(strs); i++ {
		// 剪枝
		if i != index && strs[i] == strs[index] {
			continue
		}
		// 递归处理下一层
		strs[i], strs[index] = strs[index], strs[i]
		dfs(strs, index+1, result)
	}
	for i := len(strs) - 1; i > index; i-- {
		strs[i], strs[index] = strs[index], strs[i]
	}
}