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]);

        }   

    }   

}