2973:Scrabble

keyword

C

概要

_とアルファベットで構成された文字列が与えられる。その文字列のいくつかをつくって別の文字列がつくれるかどうか判定する問題。_はワイルドカードとして使える。
_以外の文字を使えるだけ使って処理しきれなかった文字の数と_の数を比較すれば良い。

char dict[1002][26];
char line[10];
char tile[26];

int main(){
    int i, j, n, ans, cnt, any;
    while(scanf("%d\n",&n),n){
        for(i=0;i<n;i++) memset(dict[i],0,sizeof(dict[i]));
        memset(tile,0,sizeof(tile));
        for(i=0;i<n;i++){
            scanf("%s\n",line);
            for(j=0;line[j];j++)
                dict[i][line[j]-'A']++;
        }

        scanf("%s\n",line);
        any = 0;
        for(j=0;line[j];j++){
            if('A'<=line[j]&&line[j]<='Z')
                tile[line[j]-'A']++;
            else
                any++;
        }

        ans = 0;
        for(i=0;i<n;i++){
            cnt = 0;
            for(j=0;j<26;j++){
                cnt += (dict[i][j]>tile[j])?(dict[i][j]-tile[j]):0;
            }
            if(any >= cnt)
                ans++;
        }

        printf("%d\n",ans);
    }
}