剑指offer面试题38：字符串的排列（golang实现）

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例：

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
           

限制

1 <= s 的长度 <= 8
           

Leetcode链接：剑指offer面试题38：字符串的排列

算法分析

• 通过回溯法得到字符串s的全排列，通过for循环每次在s中选择一个字符，在递归调用中将该字符从s中去掉加入item中，重复该操作，直到传入backtrack中的字符串长度小于等于0，说明此时得到了s的一个排列，将其加入结果res中。
• 为防止出现重复的item，在每轮递归用一个map对每次选中的字符进行统计，如果当前字符在map中已经存在，则剪枝跳过本次循环，确保每一次递归调用中item的同一个位置不能出现相同的字符

复杂度分析

问题规模： 字符串s的长度n

• 时间复杂度：O( n ! ∗ n n!*n n!∗n)，s共有n!个全排列，每一轮排列需要花费O( n n n)时间
• 空间复杂度：O( n 2 n^2 n2)，每轮递归用到了一个map来记录当前位置某个字符是否出现，最坏情况下（即字符串s中所有字符皆不相同）需要记录所有字符。所以额外空间大小为n+(n-1)+(n-2)+ ···+2+1 ≈ n^2

Golang代码如下

func backtrack(s, item string) (res []string) {
	count := make(map[byte]bool)
	if len(s) <= 0 {
		res = append(res, item)
	} else {
		for i := 0; i < len(s); i++ {
			if _, ok := count[s[i]]; !ok {
				count[s[i]] = true
				res = append(res, backtrack(s[:i] + s[i+1:], item + string(s[i]))...)
			}
		}
	}
	return
}

func permutation(s string) (res []string) {
	if len(s) == 0 {
		return []string{}
	}
	return backtrack(s, "")
}