字符串的排列:(动态规划)
首先,C++ STL库中的next_ermutation()函数正好可以完成这个功能。
例如:next_ermutation函数
使用这个函数的代码如下:
vector<string> Permutation(string str) { if (str.empty()) return {}; sort(str.begin(),str.end()); vector<string> ans; ans.push_back(str); while(next_permutation(str.begin(),str.end())) ans.push_back(str); return ans; }
当然,做算法题肯定不能用这个方法, 但可以学习补充下。
之所以用动态规划,是因为我们需要得到最终的组合情况, 而这个问题,一般可以分解为子问题完成:
例如:
{a,b}的组合情况
{a,b,c}的组合情况为:
边界条件是,一个字母,
其余则按照前后,组合
针对重复的字母,如{a,b,c,c}
其中f(c1,f(a,,b,c2)) = f(c2,f(a,b,c1)).
所以在构建关系时,引入一个标记。
class Solution { public: vector<string> Get_perm(string str){ vector<string> ans; //DP边界条件,只有一个的时候 if (str.size() == 1){ ans.push_back(str); return ans; } //---处理标记,用于去重 vector<string> f_sub; stack<char> flag; for(int i=str.size(); i>=0; --i) if (flag.empty()){ flag.push(str[i]); }else if(str[i] != flag.top()){ flag.push(str[i]); } //----计算res(str) = res(char_i) + res(str_sub) for(int i=0; i<str.size(); i++){ if(str[i] == flag.top()){ //去重 flag.pop(); //当前字母 string char_i = str.substr(i,1); //剩余字符串 string s_1 = str.substr(0,i); string s_2 = str.substr(i+1, str.size()-i-1); string str_sub = s_1 + s_2; //获取剩余字符串的res(str_sub) f_sub = Get_perm(str_sub); //计算res(str) for(int j=0; j<f_sub.size(); j++) ans.push_back(char_i + f_sub[j]); } } return ans; } vector<string> Permutation(string str) { vector<string> res; if(str.size()==0) return {}; //排序确认 sort(str.begin(), str.end()); res = Get_perm(str); sort(res.begin(), res.end()); return res; } };
当然还有其他的方法,但本题主要考察和练习动态规划的思想和抽象。