String Permutations

1. Problem Description

Given a string, print all permutations of its characters in lexicographic order. For example, given the string abc, print all strings formed by a, b, and c in lexicographic order: abc, acb, bac, bca, cab, and cba.

2. Approach

• Recursion + backtracking

3. Implementation

package main

import "sort"

/**
 * The class name, method name, and parameter names in the code have already been specified. Do not modify them; directly return the value required by the method.
 *
 * @param str string
 * @return one-dimensional string array
 */
// Time: O(N·N!·log(N!))
// Space: O(N·N!)
func Permutation(str string) []string {
	if len(str) == 0 {
		return nil
	}

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


	// Deduplicate
	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
	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. References

• String Permutations - NowCoder