アナグラム 文字の並び替え

anagram.png

文の中の文字をいくつか入れ替えることによって全く別の意味にさせる遊びのこと
コーディングクイズによく出てくる典型的なお題だよ
たとえばこんなかんじでお題が出ます

2つの文字列が与えられたとき、片方がもう片方の並び替えになっているかどうかを決定する関数を書いてください

まず関数の形はこんなかんじにしようかな

 //片方がもう片方の並び替えになっているかどうかを返す関数
 bool isSortedFrom(char* src,char* sorted){
      // ......
      return true or false;
 }

まずは、2つの文字列の長さが違ったら明らかにfalse!

なのでとりあえずこういうコードが書き足せます

 //片方がもう片方の並び替えになっているかどうかを返す関数
 bool isSortedFrom(string src,string sorted){
    if(src.size()!=sorted.size()){
         return false;
    }
 }

解法は2つ

  1. 両方の文字列をソートして全く同じかどうか比較する
  2. 文字のヒストグラムを作って同じかどうか比較する

1.は非常に簡潔でわかりやすく、コードの量が少なくて済むけど、速さ的にイマイチかもしれない。
2.は書くコードの量が多くて読みにくいけど、1より速度が速そうです。

ヒストグラムを作る方法

C言語限定で書きました

 //片方がもう片方の並び替えになっているかどうかを返す関数
 bool isSortedFrom(char* src,char* sorted){
     int* histgram=new int[256];
     int* histgramB=new int[256];
     for(int i=0;i<256;i++){
         histgram[i]=0;
         histgramB[i]=0;
     }
 
     while(*src!='\0'){
        histgram[*src++]++;
     }
 
      while(*sorted!='\0'){
          histgramB[*sorted]++;
           sorted++;
     }
       bool check=true;
      for(int i=0;i<256;i++){
          if(histgram[i]!=histgramB[i]){
              check=false;
          }
     }
      return check;
 }

サポートサイト Wikidot.com