文字列の中で同じ文字があるかどうか見つける

duplicate-string.png

全部英語のアルファベットかつASCIIコードという前提で話を進めます

コツ 文字列の長さが256以上長かったら、すべてが違う文字だということはありえない!

問題に夢中になって解こうとしてると、見失いがちの盲点ですが、
文字列の長さが256以上長かったら、すべてが違う文字だということはありえません。なので即returnできます★これで高速化ポイントひとつゲットですね

 bool isUniqueChars(string teststr){
     if(teststr.size()>256){return false;}
    //これから作るところ~続きは下へ
}
void main(){

最も簡単で単純な方法

  bool isUniqueChars(string teststr){
     if(teststr.size()>256){return false;}
    bool sameFlag=true;//重複があったらfalse
    for(int i=0;i<teststr.size();i++){
        for(int c=0;c<teststr.size();c++){
            if(c==i){continue;}
            if(teststr[c]==teststr[i]){
                sameFlag=true;
            }
        }
    }//end i
    return sameFlag;
}
void main(){

もっとも考えるのが簡単だけど、遅い方法です

もっと効率的にしてみよう たとえば、bool型の配列を使ってみるのは?

日本語で考えるとなかなか思いつきませんが、
英語のアルファベットASCIIは文字数が少ないというのが特徴。これを活かしていろいろ高速化できます。

Step1. bool[256]サイズの配列を作る。

そして、登場したかどうかフラグを立てます

 bool isUniqueChars(string teststr){
     if(teststr.size()>256){return false;}
     bool* appearedFlags=new bool[256];
    for(int i=0;i<teststr.size();i++){
        if(appearedFlags[teststr[i]]){//重複発見★
            return false;
        }
        appearedFlags[teststr[i]]=true;
    }//end i
    return true;
}

こっちの方がより高速ですね。boolで登場したかどうか印をつけるテーブルを作ってますからね

string

サポートサイト Wikidot.com string