牛客网 面试笔试 TOP101    |     LeetCode 3437. 全排列III

1. 题目

描述

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

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

输入描述：

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

示例1

输入：

"ab"

返回值：

["ab","ba"]

说明：

返回["ba","ab"]也是正确的          

示例2

输入：

"aab"

返回值：

["aab","aba","baa"]

示例3

输入：

"abc"

返回值：

["abc","acb","bac","bca","cab","cba"]

示例4

输入：

" "

返回值：

[ ]

2. 解题思路

字符串的排列可以使用回溯算法，要注意字符串中有可能包含相同的字符。具体思路如下：

遍历每一个元素，以该元素作为开头的数字数列。首先选取该数字，并标记该数字已经使用过；再递归选择其他数字；撤销该数字，让其他数字作为开头。缩小数字区间：该元素已经使用过；当前元素与前一个元素一样，且前一个已经使用过。

如果文字描述的不太清楚，你可以参考视频的详细讲解。

• Python版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1374917

• Java版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1368181

• Golang版本：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1365124

3. 编码实现

核心代码如下：

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param str string字符串* @return string字符串一维数组*/
func Permutation(str string) []string {// write code hereresult = make([]string, 0)path = make([]string, 0)//字符串为数组arr := strings.Split(str, "")sort.Strings(arr)mark = make([]bool, len(arr))//回溯获取结果backtracking(arr)return result
}var (result []string //结果集path   []string //路径mark   []bool
)func backtracking(arr []string) {// 2. 递归终止条件：路径数组满了（找到一种路径）,加入到输出列表if len(path) == len(arr) {//2.1 存放结果tmp := strings.Join(path, "") //切片转stringresult = append(result, tmp)//2.2 返回return}//1.选择：在本层集合中遍历元素for i := 0; i < len(arr); i++ {//1.4剪枝：// 1.4.1 元素已经使用过则不需要再加入了if mark[i] {continue}// 1.4.2 当前的元素charStr[i]与同一层的前一个元素charStr[i-1]相同且charStr[i-1]已经用过了if (i >= 1) && (arr[i] == arr[i-1] && mark[i-1]) {continue}//1.1 处理节点 （选取字符）path = append(path, arr[i]) //加入路径数组mark[i] = true              //标记为使用过// 1.2 递归（选择其他字符）backtracking(arr)//1.3 回溯，撤销选择path = path[:len(path)-1]mark[i] = false}
}

具体完整代码你可以参考下面视频的详细讲解。

• Python版本：哔哩哔哩_bilibili

• Java版本：哔哩哔哩_bilibili

• Golang版本：哔哩哔哩_bilibili

4.小结

字符串的排列可以使用回溯算法，要注意字符串中有可能包含相同的字符。遍历每一个元素，以该元素作为开头的数字数列。首先选取该数字，并标记该数字已经使用过；再递归选择其他数字；撤销该数字，让其他数字作为开头。

《数据结构与算法》深度精讲课程正式上线啦！7 大核心算法模块全解析：

  ✅   链表

  ✅   二叉树

  ✅   二分查找、排序

  ✅   堆、栈、队列

  ✅   回溯算法

  ✅   哈希算法

  ✅   动态规划

无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

• Python编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss897667807

• Java编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss161443488

• Golang编码实现：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss63997

对于数据结构与算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句：黄沙百战穿金甲，不破楼兰终不还。