一、字符的全排列
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
class Solution {
public:
vector<string> Permutation(string str) {
vector<string>a;
if(str.size()==0)
return a;
Permutation(a,str,0);
sort(a.begin(),a.end());
return a;
}
void Permutation(vector<string>& a,string str,int begin){
if(begin==str.size()-1)
a.push_back(str);
for(int i=begin;i<str.size();i++){
if(i!=begin && str[i]==str[begin])
continue;
swap(str[begin],str[i]);
Permutation(a,str,begin+1);
swap(str[begin],str[i]);
}
}
};
#include <iostream>
using namespace std;
void FullSort(string str,int m,int n)
{
if(m==n-1){
cout<<str<<endl;
return;
}
for(int i=m;i<n;i++){
swap(str[m],str[i]);
FullSort(str,m+1,n);
}
}
int main()
{
string str="abc";
FullSort(str,0,3);
return 0;
}
二、字符的组合
输入一个字符串,求字符的所有组合。例如:输入abc,则它们的组合有a、b、c、ab、ac、bc、abc。其中ab和ba只是一种组合。
class Solution{
public:
vector<string> combination(string str){
vector<string> a;
if (str.size() == 0)
return a;
string tmp;
for (int i = 1; i < str.size(); i++)
recur(str, tmp, 0, i, a);
return a;
}
void recur(string str, string &tmp, int start, int number, vector<string>& a){
if (number > str.size() - start) {
return;
}
tmp.push_back(str[start]);
recur(str, tmp, start + 1, number - 1, a);
tmp.pop_back();
recur(str, tmp, start + 1, number, a);
}
};
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
void combination(char* ptr, int n, vector<char> &result)
{
if (ptr == NULL) return;
if (n == 0) {
vector<char>::iterator iter = result.begin();
for (; iter != result.end(); iter++){
cout << *iter;
}
cout << endl;
return;
}
if (*ptr == '\0') return;
result.push_back(*ptr);
combination(ptr + 1, n - 1, result);
result.pop_back();
combination(ptr + 1, n, result);
}
int main()
{
char str[] = "abc";
vector<char> result;
int i;
int length = strlen(str);
for (i = 1; i <= length; ++i)
{
combination(str, i, result);
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)