字符串的排列（Python and C++解法）

题目：

输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof

思路：

　　根据字符串排列的特点，考虑深度优先搜索所有排列方案，先固定第 1位字符、再固定第 2 位字符、... 、最后固定第 n 位字符。

需要注意：当字符串存在重复字符时，排列方案中也存在重复的结果，为排除重复方案，需保证每种字符只在此位置固定一次，即剪枝。

Python解法：

 1 class Solution:
 2     def permutation(self, s: str) -> List[str]:
 3         res = []
 4         ch = list(s)  # 转换为字符列表，方便后续交换
 5 
 6         def dfs(x):
 7             if x == len(ch)-1:  # 已经固定到最后一位
 8                 res.append(''.join(ch))
 9                 return
10             st = set()
11             for i in range(x, len(ch)):
12                 if ch[i] in st:  # 每个字符只固定一次，滤除输入中重复的字符，以避免产生重复的结果
13                     continue
14                 st.add(ch[i])
15                 ch[i], ch[x] = ch[x], ch[i]  # 将ch[i]字符固定在第x位
16                 dfs(x+1)  # 递归固定后面的字符
17                 ch[i], ch[x] = ch[x], ch[i]  # 还原交换
18         dfs(0)
19         return res

C++解法：

 1 class Solution {
 2 public:
 3     vector<string> res;
 4     vector<char> c_char;
 5     vector<string> permutation(string s) {
 6         for(int i = 0; i < s.size(); i++)  // string转换成vector<char>字符数组
 7             c_char.push_back(s[i]);
 8         dfs(0);
 9         return res;
10     }
11 
12     void dfs(int x) {
13         if(x == c_char.size()-1) {
14             string tempRes(c_char.begin(), c_char.end());  // 字符数组转换为string
15             res.push_back(tempRes);
16             return;
17         }
18         set<char> st;
19         for(int i = x; i < c_char.size(); i++) {
20             if(st.count(c_char[i]) == 1)  // 判重，避免输入中重复的元素导致最终结果重复
21                 continue;
22             st.insert(c_char[i]);
23             swap(c_char[i], c_char[x]);  // 交换两个同类型向量的数据
24             dfs(x+1);  // 交换完之后继续递归全排列
25             swap(c_char[i], c_char[x]);  // 回溯前需要恢复交换的字符
26         }
27     }
28 };