首页 > 代码库 > careercup-递归和动态规划 9.5
careercup-递归和动态规划 9.5
9.5 编写一个方法，确定某字符串的所有排列组合。
类似leetcode：Permutations
解法：
跟许多递归问题一样，简单构造法非常管用。假设有个字符串S，以字符序列a1a2a...an表示。
终止条件：n=1
S=a1，只有一种排列组合，即字符串a1
情况：n=2
S=a1a2 有两种排列组合a1a2和a2a1
情况：n
对于一般情况下，我们只需重复这个步骤。即已经求得f(n-1)的解，接着只要将an插入到这些字符串的任意位置。
c++代码实现：
#include<iostream>#include<vector>#include<string>using namespace std;vector<string> getPerms(string str){ if(str.empty()) return vector<string>(); int n=str.length(); vector<string> res; res.push_back(string("")); vector<string> r; int i,j; for(i=0;i<n;i++) { char c=str[i]; r=res; res.clear(); for(j=0;j<r.size();j++) { string tmp=r[j]; int index=0; while(tmp.begin()+index!=tmp.end()) { tmp.insert(tmp.begin()+index,c); res.push_back(tmp); tmp=r[j]; index++; } tmp.push_back(c); res.push_back(tmp); } } return res;}int main(){ string str="abc"; vector<string> res=getPerms(str); for(auto s:res) cout<<s<<endl;}
careercup-递归和动态规划 9.5
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。