38.md

字符串的排列

题目

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组 例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB

数据范围：n < 10 要求：空间复杂度 O(n!)，时间复杂度 O(n!)

输入描述： 输入一个字符串,长度不超过10,字符只包括大小写字母

示例

输入："ab" 返回值：["ab","ba"] 说明：返回["ba","ab"]也是正确的

思路

• 假设你手里有一把麻将牌[n]个，你要枚举所有的排列组合
• 首先把每张牌分别放在首位，这时需要做一个替换，得到[n]个结果
• 然后这[n]个组合都保持首位不变，把剩下的作为一把新麻将牌[子问题]来处理
• 递归 + map 排重

实现

func Permutation(str string) []string {
	var result []string
	if str == "" {
		return result
	}
	length := len(str)
	strByte := []byte(str)
	var handler func(int)
	handler = func(i int) {
		if i != length {
			// 用 map 排重
			strMap := make(map[string]int)
			for j := i; j < length; j++ {
				_, ok := strMap[string(strByte[j])]
				if !ok {
					strMap[string(strByte[j])] = 1
					// 把首位和剩下的依次做替换
					strByte[i], strByte[j] = strByte[j], strByte[i]
					// 把剩下的作为一个[子问题]递归处理
					handler(i + 1) // +1 决定了多锁定一位
					// 切换过的要换回来迎接下一位
					strByte[i], strByte[j] = strByte[j], strByte[i]
				}
			}
		} else {
			// 每一位都替换了才可以加入结果集
			result = append(result, string(strByte))
		}
	}
	handler(0)
	return result
}