题解 | #字符串的排列#
字符串的排列
https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7
package main import ( "sort" "strings" ) /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str string字符串 * @return string字符串一维数组 */ func Permutation(str string) []string { // write code here var ret []string if len(str) == 0 { return ret } arr := strings.Split(str, "") // 排序后重复的字符就会相邻 sort.Strings(arr) // 用于组装临时字符串 var tmp []string // 标记每个位置的字符是否被使用过 visited := make([]bool, len(arr)) var backtrack func(arr []string, tmp []string, visited []bool) backtrack = func(arr []string, tmp []string, visited []bool) { if len(tmp) == len(arr) { ret = append(ret, strings.Join(tmp, "")) return } // 遍历所有元素选取一个加入 for i := 0; i < len(arr); i++ { // 该元素已经被加入了 if visited[i] { continue } // 重复的字符使用过了 if i > 0 && arr[i] == arr[i-1] && visited[i-1] { continue } visited[i] = true tmp = append(tmp, arr[i]) backtrack(arr, tmp, visited) // 回溯 visited[i] = false tmp = tmp[:len(tmp)-1] } } backtrack(arr, tmp, visited) return ret }