剑指38题解 | #字符串的排列#
字符串的排列
https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7
#include <vector> class Solution { public: // vector<string> sum; // void find(string& s, int& id, string& v, vector<int>& vis) // { // v+=s[id]; // if(id == s.size()-1){ // sum.push_back(v); // return; // } // for(int i = id; i < s.size(); ++i) // { // swap(s[id], s[i]); // id +=1; // find(s,id, v, vis); // } // } vector<string> Permutation(string str) { // write code here // 写的有问题的递归做法 // if (str.empty()) { // return sum; // } // int i = 0; // string v; // vector<int> vis(str.size(), 0); // 记录遍历过情况 // find(str, i, v, vis); // return sum; // // 方法1:偷懒解法,next_permutation全排列接口 // vector<string> v; // sort(str.begin(), str.end()); // do{ // v.push_back(str); // }while (next_permutation(str.begin(),str.end())); // return v; // 方法2:用过一个剔除一个做法 set<string> res; string s; find(res, str, s); vector<string> v(res.begin(), res.end()); return v; } // 全排序能想到这种方法,脑瓜子真好 void find(set<string>& res, string str, string s){ if (str.empty()) res.insert(s); for(int i = 0; i < str.size(); ++i) // 每一个位置都有可能剔除 { string tmp = str; find(res, tmp.erase(i,1), s+str[i]);// 用过的剔除,剔除的保存在新的组合字符串里面 } } };
挤挤刷刷! 文章被收录于专栏
记录coding过程