Algorithm問題を解く 8 - ハッシュ2

問題

You are required to write a method that takes two text documents: an anonymous letter L and text from a magazine M. Your method is to return true if L can be written using M and false otherwise.
(if a letter appears k times in L, it must appear at least k times in M. )
(Algorithm for interviewsより引用)

ヒント

マガジンMから部分文字列Lを取り出せという問いではないことに注意．

解答

#include <string>
#include <iostream>
#include <map>
using namespace std;

class Dict {
private:
 map<char,int> mD;
 void AddOrIncrement(char ch);
public:
 Dict() {};
 bool Analyze(string l,string m);
};

void Dict::AddOrIncrement(char ch) {
 if( mD.find(ch) != mD.end() )
  mD[ch]++;
 else
  mD[ch] = 1;
}

bool Dict::Analyze(string l, string m) {

 mD.clear();

 for( unsigned int i = 0;i < m.size();i++ ) {
  AddOrIncrement(m.at(i));
 }
 for( unsigned int i = 0;i < l.size();i++ ) {
  mD[l.at(i)]--;
  if( mD[l.at(i)] < 0 )
   return false;
 }
 return true;

}


int main() {

 Dict d;
 cout << d.Analyze("wanco", "wanchan coco ni oide") << endl;
 cout << d.Analyze("nyanco", "wanchan coco ni oide") << endl;

 return 0;

}