【アルゴリズム】秘密の文章を作れるか？javascriptで実装する

海外だとHarmless Ransom Noteと言って超有名な問題です。要は雑誌の単語を切り抜いて、脅迫状が作れるか？って問題です。

↑こんな感じですね。

問題に置き換えると。

問題：指定する文章Bの単語から、文章Aは作成可能か？文章Bの一つの単語は二回使えないとする。true/falseで判定せよ。

文章 A："this is a secret note for you from a secret admirer",

文章 B："puerto rico is a place of great wonder and excitement it has many secret waterfall locatoins that i am an admirer of you must hike quite a distance to find the secret places as they are far from populated areas but it is worth the effort a tip i have for you is to go early in the morning when it is not so hot out also note that you must wear hiking boots this is one of the best places i have ever visited"

問題は自体は簡単ですね。まずは自力で解いてみましょう。注意点は、単語の存在を真偽判定しただけではダメです。登場回数までも満たしていないといけません。

また、解法にあたり、かなり重要なコンセプトが登場します。これは使えるのでマスターすべし。

実装例

function harmlessRansomNote(noteText, magazineText) {
 var noteArr = noteText.split(" ");
 var magazineArr = magazineText.split(" ");
 var magazineObj = {};

 magazineArr.forEach(word => {
   if (!magazineObj[word]) magazineObj[word] = 0;
   magazineObj[word]++;
 });

 var noteIsPossible = true;

 noteArr.forEach(word => {
   if (magazineObj[word]) {
     magazineObj[word]--;
     if (magazineObj[word] < 0) noteIsPossible = false;
   } else {
     noteIsPossible = false;
   }
 });

 return noteIsPossible;
}

O(n)

ポイントとなるは、key・valueペアのマッピングが作れるかどうかです。まず、雑誌（引数：magazineText）の単語が何回登場数するかを、オブジェクトに格納しましょう。　

 var magazineObj = {};

 magazineArr.forEach(word => {
   if (!magazineObj[word]) magazineObj[word] = 0;
   magazineObj[word]++;
 });

これをconsole.log()すると↓ができると思います。puertoが１回、ricoが1回、isが5回って読みます。このマッピング表を作成できるかがキーです。

{ puerto: 1,
 rico: 1,
 is: 5,
 a: 3,
 place: 1,
 of: 3,
 great: 1,
 wonder: 1,
 and: 1,
 excitement: 1,
 it: 3,
 has: 1,
 many: 1,
 secret: 2,
 waterfall: 1,

次に、作成したい文章Aをループにかけて、先ほど作ったmagazineObjと比べて行きます。magazineObj[word]というのがmagazineObjのvalue：登場回数ですね。

登場すれば、減算して行きます。ここで作りたい文章の単語が、足りているか評価しているわけです。if (magazineObj[word] < 0)で、0以下になったら「もう単語が足りないよ〜」って意味なのでfalseですね。最後にelseで、そもそも単語がなかったらfalseです。

var noteIsPossible = true;

 noteArr.forEach(word => {
   if (magazineObj[word]) {
     magazineObj[word]--;
     if (magazineObj[word] < 0) noteIsPossible = false;
   } else {
     noteIsPossible = false;
   }
 });

 return noteIsPossible;

念のため、実行時。

 harmlessRansomNote(
   "this is a secret note for you from a secret admirer",
   "puerto rico is a place of great wonder and excitement 
　　it has many secret waterfall locatoins that i am an admirer 
　　of you must hike quite a distance to find the secret places as they 
　　are far from populated areas but it is worth the effort a tip 
　　i have for you is to go early in the morning when it is not so 
　　hot out also note that you must wear hiking boots this is one
　 of the best places i have ever visited"
 )

なぜオブジェクトにあらかじめマッピングするかというと、高速だからです。ループを二重にまわして、同時に評価していく方法もあります。それだとO(n^2)で、文章Aの単語が10個で文章Bが100個だとしたら、10 * 100 = 1000回のループになります。

データ量が少なければ良いのですが、データ量が増えた場合、指数関数的に計算量が増えて行きます。

今回と場合だと、単発のループなので、ループする回数は最悪でも文章Bのデータ量分だけすみます。O(n)ですね。

O-記法で計算量の測りかたは、転載予定なので楽しみにしていてください。

javascriptで難易度高めの問題に挑戦したい人は、こちらの本がオススメです。

もっとプログラマ脳を鍛える数学パズル アルゴリズムが脳にしみ込む70問