零、原題鏈接

面試題 08.08. 有重復字符串的排列組合

一、題目描述

有重復字符串的排列組合。編寫一種方法，計算某字符串的所有排列組合。

二、測試用例

示例 1：

 輸入：S = "qqe"輸出：["eqq","qeq","qqe"]

示例 2：

 輸入：S = "ab"輸出：["ab", "ba"]

提示:

字符都是英文字母。
字符串長度在[1, 9]之間。

三、解題思路

1. 基本思路：
   ??使用回溯法，在利用散列表去重
2. 具體思路：
   • 編寫 dfs 函數
     • 如果字符串每個位置的元素都確定，則記錄字符串到答案中。
     • 創建散列表
     • 確定第 k 個位置的字符，從第 k+1 到尾部選取一個字符進行交換
       • 如果散列表中存在該字符，表示重復，則跳過
       • 散列表記錄該字符
       • 與第 k 個位置的字符交換
       • 遞歸確定第 k+1 個字符
       • 恢復狀態
   • 調用 dfs 函數，返回結果。

四、參考代碼

時間復雜度：$\mathrm{O}(n!)$【n 是字符串長度】
空間復雜度：$\mathrm{O}(n)$

class Solution {
public:string str;vector<string> ans;void dfs(const int& k) {if (k == str.length()) {ans.emplace_back(str);return;}vector<bool> m(128, false);for (int i = k; i < str.length(); i++) {if (m[str[i]])continue;m[str[i]] = true;swap(str[k], str[i]);dfs(k+1);swap(str[k], str[i]);}}vector<string> permutation(string S) {str = S;dfs(0);return ans;}
};