Description
The game of Scrabble is played with tiles. A tile either has a single letter written on it, or it is blank. In the latter case, the tile may be used to represent a letter of your choice. On your turn, you arrange the tiles to form a word. Each tile may be used at most once, but not all tiles need to be used. Given several Scrabble tiles and a dictionary, determine how many words in the dictionary can be formed using the given Scrabble tiles.
Input
The input test file will contain multiple test cases. In each test case, the first line contains a positive integer n ≤ 1000 indicating the number of words in the dictionary. The following n lines each contain a single string with between 1 and 7 uppercase letters, representing a word in the dictionary. No word will appear in the dictionary twice. The next line contains a single string giving the tiles you have available. It will contain only capital letters, representing tiles with that letter on it, and underscores, representing blank tiles. The string will contain between 1 and 7 characters, possibly including duplicate tiles. The end-of-file is marked by a test case with n = 0 and should not be processed.
Output
For each test case, write a single line with the number of dictionary words that can be spelled with the given Scrabble tiles.
Sample Input
5 PROGRAM CONTEST PIZZA ZA PITA _PIZA 3 BANANAS CARROTS FIGS A__AA__ 0Sample Output
3 2Hint
In the first test case, PIZZA, ZA and PITA can be spelled as PIZ_A, ZA and PI_A. There are not enough letters to spell PROGRAM or CONTEST. In the second test case, BANANAS and FIGS can be spelled as _A_A_A_ and ____. On the other hand, CARROTS would require 6 blanks in addition to the A.
#include<iostream>#include<algorithm>using namespace std;int comp(char &a,char &b){return a<b;}int main(){int n;char dic[1005][10];char temp[10];int i,j,k;int match;int blank;int pos;int res;while(1) { cin>>n;if(n==0)break;for(i=0;i<n;i++) { cin>>temp; sort(temp,temp+strlen(temp),comp); strcpy(dic[i],temp); } cin>>temp; blank=0; sort(temp,temp+strlen(temp),comp);for(i=0;i<strlen(temp);i++) {if(temp[i]=='_') blank++; } res=0;for(k=0;k<n;k++) { pos=-1; match=0;for(i=0;i<strlen(dic[k]);i++) {for(j=pos+1;j<strlen(temp)-blank;j++) {if(dic[k][i]==temp[j]) { pos=j; match++;break; } } }if(strlen(dic[k])-match<=blank) { res++; } } cout<<res<<endl; }return 0;}
转载于:https://www.cnblogs.com/w0w0/archive/2011/11/22/2258743.html
相关资源：数据结构—成绩单生成器