三种方法;
- 基于库函数
next_permutation(begin, end)
- 去重方法:先sort初始字符串再处理(本题初始字符串已经有序)
- 基于回溯
- 通过一个visited数组记录已经被选中的位置
- 去重方法:通过set进行去重
- 基于交换
- 去重方法:通过set进行去重
方法一的代码:
// // Created by jt on 2020/9/18. // #include <string> #include <vector> #include <algorithm> using namespace std; class Solution { public: vector<string> Permutation(string str) { vector<string> res; if (str.size() < 1) return res; do { res.push_back(str); } while (next_permutation(str.begin(), str.end())); return res; } };
方法二的代码:
// // Created by jt on 2020/9/18. // #include <string> #include <vector> #include <set> using namespace std; class Solution { public: vector<string> Permutation(string str) { vector<string> res; if (str.size() < 1) return res; vector<int> visited(str.size(), 0); string tmp; set<string> st; backtrace(st, visited, str, 0, tmp); for (auto &a : st) res.push_back(a); return res; } void backtrace(set<string> &st, vector<int> &visited, string &str, int pos, string tmp) { if (pos == str.size()) { st.insert(tmp); return; } for (int i = 0; i < str.size(); ++i) { if (visited[i] == 1) continue; else { visited[i] = 1; tmp.push_back(str[i]); backtrace(st, visited, str, pos+1, tmp); tmp.pop_back(); visited[i] = 0; } } } };
方法三:
// // Created by jt on 2020/9/18. // #include <string> #include <vector> #include <set> using namespace std; class Solution { public: vector<string> Permutation(string str) { vector<string> res; if (str.size() < 1) return res; set<string> st; backtrace(st, str, 0); for (auto &a : st) res.push_back(a); return res; } void backtrace(set<string> &st, string &str, int pos) { if (pos == str.size() - 1) { st.insert(str); return; } for (int i = pos; i < str.size(); ++i) { if (i != pos && str[i] == str[pos]) continue; swap(str[pos], str[i]); backtrace(st, str, pos+1); swap(str[pos], str[i]); } } };