C++で指定されたすべての文に共通して存在する単語の数を数える方法

複数の文(文字列)が与えられたとき、すべての文に共通して存在する単語の数を数えるのがこの記事の目的です。

注: 判定の対象となるのは、すべて小文字で構成された単語のみです。

問題の具体例

たとえば、次の3つの文があったとします。

• "I am learning C language"
• "learning new things is easy"
• "Kids are learning healthy habits"

3つの文すべてに登場するのは「learning」だけなので、答えは 1 になります。

入力・出力例

例1

入力: "The clothes were dry"、"All the kids were playing"、"Those were the best days"

出力: すべての文に存在する単語の数 − 2

説明: 「the」と「were」がすべての文に含まれています。

例2

入力: "We are going to school"、"If you are willing then continue"、"All these are sold"

出力: すべての文に存在する単語の数 − 1

説明: 「are」がすべての文に含まれています。

アルゴリズムのアプローチ

ここで紹介する手法では、まず最初の文に含まれる単語を vector<pair<string, bool>> 型の set に格納します。続いて、unordered_map<string, bool> 型の check マップを使い、それ以外の各文に同じ単語が存在するかどうかを順番に検証していきます。

• vector<string> vec を宣言し、文を表す文字列で初期化します。
• 文の総数は vec.size() で求められます。
• 関数 words_sentences(vector<string> vec, int size) は、文のベクターとそのサイズを受け取り、すべての文に存在する単語の数を返します。
• 初期値として count を 0 に設定します。
• 一時的な文字列 str を用意し、文から切り出した個々の単語を一時的に保持します。
• while ループで vec[0] に格納された最初の文を走査します。
• 内側の while ループで、空白文字にぶつかるまで1文字ずつ str に追加し、1単語を切り出します。
• 単語が取り出せたら、ペア (str, true) を set に push_back します。
• これを vec[0] 内のすべての単語に対して繰り返します。
• この時点で、set には最初の文の全単語と true のペアが格納されています。
• for ループ(j = 1 から j < size まで)で、2番目以降の文を順に処理します。
• 現在の文 vec[j] から各単語を切り出して str に格納します。
• check[str] = true として、その単語が出現したことをマークします。
• 現在の文のすべての単語に対して同じ処理を繰り返します。
• for ループで set を走査し、現在の文の check に登録されている単語が set にも存在するかを確認します。
• もう一度 for ループで set を走査します。
• ある単語がすべての文に出現しているなら set[k].second は true のまま残ります。true であれば count をインクリメントします。
• 最終的に count には、すべての文に共通する単語の数が入っています。
• count を結果として返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int words_sentences(vector<string> vec, int size){
   int count = 0;
   int i = 0;
   string str;
   unordered_map<string, bool> check;
   vector<pair<string, bool>> set ;
   pair<string, bool> str_bool;
   while (i < vec[0].size()){
      str = "";
      while (i < vec[0].size() && vec[0][i] != ' '){
         str += vec[0][i];
         i++;
      }
      i++;
      if (str != ""){
         str_bool = make_pair(str, true);
         set.push_back(str_bool);
      }
   }
   for (int j = 1; j < size; j++){
      check.clear();
      i = 0;
      while (i < vec[j].size()){
         str = "";
         while (i < vec[j].size() && vec[j][i] != ' '){
            str += vec[j][i];
            i++;
         }
         i++;
         if (str != ""){
            check[str] = true;
         }
      }
      for(int k = 0; k < set.size(); k++){
         if (set[k].second != false && check[set[k].first] == false){
            set[k].second = false;
         }
         else if (set[k].second != false && check[set[k].first] == true){
            check[set[k].first] = false;
         }
      }
   }
   for (int k = 0; k < set.size(); k++){
      if (set[k].second == true){
         count++;
      }
   }
   return count;
}
int main(){
   vector<string> vec;
   vec.push_back("Honesty is the best policy");
   vec.push_back("policy varies from company to company");
   vec.push_back("Employee should follow the policy of a company");
   int size = vec.size();
   cout<<"Count of words that are present in all the given sentences are: "<<words_sentences(vec, size);
   return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

Count of words that are present in all the given sentences are: 1

この例では、3つの文すべてに「policy」という単語が含まれているため、カウントは 1 となります。