题面
输入一个字符串,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
示例
1 2
| 输入:s = "abc" 输出:["abc","acb","bac","bca","cab","cba"]
|
限制
思路
dfs遍历回溯。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| class Solution { vector<string> ans; void dfs(string s, string &t, vector<bool> &vis){ if(s.size() == t.size()){ ans.push_back(t); return; } for(int i=0; i<s.size(); i++){ if(vis[i]) continue; if(i && s[i-1]==s[i] && !vis[i-1]) continue; t.push_back(s[i]); vis[i] = true; dfs(s, t, vis); vis[i] = false; t.pop_back(); } } public: vector<string> permutation(string s) { if(s.size() == 0) return {}; string t = ""; sort(s.begin(), s.end()); vector<bool> vis(s.size()); dfs(s, t, vis); return ans; } };
|