牛客網 面試筆試 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

對于數據結構與算法，我們總結了一套【可視化+圖解】方法，依據此方法來解決相關問題，算法變得易于理解，寫出來的代碼可讀性高也不容易出錯。具體也可以參考視頻詳細講解。

今日佳句：黃沙百戰穿金甲，不破樓蘭終不還。