輸入一個字符串，打印出該字符串中字符的所有排列。

你可以以任意順序返回這個字符串數(shù)組，但里面不能有重復(fù)元素。

示例

• 輸入：s = "abc"

• 輸出：["abc","acb","bac","bca","cab","cba"]

限制

• 1 <= s 的長度 <= 8

方法：回溯法

dfs方法：

• 如果是最后一位，說明是最后一種排列，轉(zhuǎn)化為字符串加入到結(jié)果中；

• 創(chuàng)建一個 HashSet 集合用于排除重復(fù)的值；

• 如果 固定的值 存在 set 集合中，代表其是重復(fù)字符，不作處理，直接跳過；

• 否則將 固定的值 加入到 set 集合中，之后用做去重處理；

• 將 固定的值 和 當前值 交換；

• 開始遞歸遍歷 下一個值；

• 遞歸完畢后，還原之前的值。

permutation方法：

• 把字符串轉(zhuǎn)化為字符數(shù)組；

• 進行遞歸遍歷；

• 返回結(jié)果字符串數(shù)組。

代碼如下：

復(fù)雜度分析

• 時間復(fù)雜度：O(N!N)，N 為字符串 s 的長度；時間復(fù)雜度和字符串排列的方案數(shù)成線性關(guān)系，方案數(shù)為 N×(N?1)×(N?2)…×2×1 ，即復(fù)雜度為 O(N!) ；字符串拼接操作 join() 使用 O(N) ；因此總體時間復(fù)雜度為 O(N!N) 。

• 空間復(fù)雜度 ：O(N的2次方) ，全排列的遞歸深度為 N ，系統(tǒng)累計使用?？臻g大小為 O(N) ；遞歸中輔助 Set 累計存儲的字符數(shù)量最多為 N+(N?1)+...+2+1=(N+1)N/2 ，即占用 O(N的2次方) 的額外空間。

END

只要功夫深，鐵杵磨成針，贈友人。

好兄弟可以點贊并關(guān)注我的公眾號“javaAnswer”，全部都是干貨。