C/C++におけるchar*とchar[]の定義の違い
1541 ワード
転載はsouldakから、微博:@evagleから
Question:
abbなどの文字列に含まれる文字のすべての可能な配列を出力します.
例えばabb出力3個:abb,bab,bba
Answer:
私たちが自分でやるとしたら、次のようにします.
1.n個の文字がn個の格子に相当する.
2.まず最初の格子を入れて、n文字の中から任意に1つを選んで、この格子に置いて、置いた後にn-1個の格子とn-1個の文字を残します
3.2番目の格子を入れ、n-1文字のうちいずれかを選択する
...
n.最後の格子は、1文字しか残っていません.選択せずに、置いた結果を出力します.
第2歩から第n歩は実は問題の本質は同じで、k文字は1つを選んで、格子の中に置くことができます.problemとsubproblemの関係なので,再帰的に解くことができる.
1.文字列sを取得し、長さnを取得する
2.ポーリングは、s[0]にどの文字を入れるかを決定し、n個を共有し、k番目に置くと、s[k]をs[0]、s[0]をs[k]に置く.
3.置いてからサブ問題を解く、すなわちs[1]~s[n-1]の配列を求める
4.既にs[n-1]まで解いた場合、出力結果
Attention:入力strはchar配列であるべきで、このように定義することはできません:char*str=“abc”;具体的には、C/C++におけるchar*とchar[]の定義の違いを参照してください.
//rm_dup: true for remove duplicated strings
void permutation(char* str, int start, bool rm_dup){
if(str==NULL||str=="")
return;
if(start==strlen(str)-1)
cout<<str<<endl;
bool visit[256];
memset(visit,0,sizeof(visit));
for(int i=start;i<strlen(str);i++){
if(!visit[str[i]]||!rm_dup){
visit[str[i]] = true;
std::swap(str[start],str[i]);
permutation(str,start+1,rm_dup);
std::swap(str[start],str[i]);
}
}
}