agl87bk
BAN USER#include<cstdio>
#include<string>
#include<set>
#include<vector>
#include<iostream>
#include<cstdlib>
using namespace std;
set< vector<char> > sequence(string s, int start, int end){
set< vector<char> > output;
if (start > end){
vector<char> seq;
output.insert(seq);
}else if (start == end){
vector<char> seq;
char singleChar[1];
singleChar[0] = s[start];
int singleDigit = atoi(singleChar);
seq.push_back(char ( 'a' - 1 + singleDigit));
output.insert(seq);
}else{
set <vector<char> > sub_output = sequence(s, start+1, end);
set <vector<char> >::iterator it = sub_output.begin();
char singleChar[1]; singleChar[0] = s[start];
char zero[1]; zero[0] = '0';
int singleDigit = atoi(singleChar);
char charFromSingleDigit = (char) ('a' - 1 + singleDigit);
for (; it != sub_output.end(); ++it){
vector<char> sub_v = (*it);
sub_v.push_back(charFromSingleDigit);
output.insert(sub_v);
}
char bothChars[2];
bothChars[0] = s[start];
bothChars[1] = s[start+1];
int bothDigits = atoi(bothChars) - atoi(zero);
if (bothDigits <= 26){
char charFromBothDigits = (char) ('a' - 1 + bothDigits);
sub_output = sequence(s, start+2, end);
it = sub_output.begin();
for (; it != sub_output.end(); ++it){
vector<char> sub_v = *it;
sub_v.push_back(charFromBothDigits);
output.insert(sub_v);
}
}
}
return output;
}
int main(){
string s;
cin >> s;
cout << "Input string is: " << s << endl;
set< vector<char> > output = sequence(s, 0, s.length()-1);
set< vector<char> >::iterator it = output.begin();
for (; it != output.end(); ++it){
for (int i = 0; i< ((*it).size()); ++i){
printf("%c", ((*it)[i]));
}
printf("\n");
}
return 0;
}
And in linear time:
- agl87bk February 10, 2013