字符串的排列

1. 题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

2. 思路

• 递归+回溯

3. 实现

package main

import "sort"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param str string字符串
 * @return string字符串一维数组
 */
//时间：O(N·N!·log(N!))
//空间：O(N·N!)
func Permutation(str string) []string {
	if len(str) == 0 {
		return nil
	}

	//排列
	permutations := make([]string, 0)
	permutation([]rune(str), 0, &permutations)


	//去重
	res := make([]string, 0)
	set := make(map[string]interface{}, 0)
	for i := 0; i < len(permutations); i++ {
		if _, ok := set[permutations[i]]; ok {
			continue
		}
		res = append(res, permutations[i])
		set[permutations[i]] = nil
	}

	//排序
	sort.Strings(res)
	return res
}

func permutation(str []rune, index int, permutations *[]string) {
	if index == len(str)-1 {
		*permutations = append(*permutations, string(str))
		return
	}

	for i := index; i < len(str); i++ {
		swap(str, index, i)

		permutation(str, index+1, permutations)

		swap(str, index, i)

	}
}

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

4. 参考

• 字符串的排列_牛客题霸_牛客网