POJ 2973 - Scrabble

http://poj.org/problem?id=2973

概要

1つのパターンに対して n 個の文字列が与えられる． パターン中のワイルドカードはどの文字にも一致するとみなす． パターンの文字を好きな数だけ好きな順番で並べた文字列が一致するとき，その文字列にマッチするとする．

n 個の文字列のうち，いくつパターンにマッチするか答える．

制約

解法

文字列中の各文字 c について，c の出現回数がパターンのそれより多い場合はいくつ多いかを数え，その総計がワイルドカードの数以下だったらマッチする，というように実装した．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 bool match(const vector<int>& s, const vector<int>& c, int wild)
 6 {
 7   for (int i = 0; i < 26; i++) {
 8     if (s[i] > 0) {
 9       if (s[i] > c[i]) {
10         wild -= s[i] - c[i];
11         if (wild < 0) {
12           return false;
13         }
14       }
15     }
16   }
17   return true;
18 }
19 
20 int main()
21 {
22   int N;
23   while (cin >> N && N != 0) {
24     vector<vector<int> > dict;
25     for (int i = 0; i < N; i++) {
26       string word;
27       cin >> word;
28       vector<int> c(26, 0);
29       for (string::const_iterator it(word.begin()); it != word.end(); ++it) {
30         ++c[*it - 'A'];
31       }
32       dict.push_back(c);
33     }
34     string tile;
35     cin >> tile;
36     int wild = 0;
37     vector<int> c(26, 0);
38     for (string::const_iterator it(tile.begin()); it != tile.end(); ++it) {
39       if (*it == '_') {
40         ++wild;
41       } else {
42         ++c[*it-'A'];
43       }
44     }
45     int ans = 0;
46     for (vector<vector<int> >::const_iterator it(dict.begin()); it != dict.end(); ++it) {
47       if (match(*it, c, wild)) {
48         ++ans;
49       }
50     }
51     cout << ans << endl;
52   }
53   return 0;
54 }
poj/2973.cc