#include <stdio.h>
#include<string.h>
#include<stdlib.h>
int strcmpfunc(const void *a, const void *b)
{
return (strcmp((char *)a, (char *)b));
}
int main()
{
int tst;
scanf("%d",&tst);
while(tst--)
{
int strings;
scanf("%d",&strings);
char str[strings][20];
int i;
for(i = 0; i<strings; i++)
scanf(" %s",str[i]);
/*Sort the array.*/
qsort(str, strings, sizeof(char)*20, strcmpfunc);
int pre_index = 0;
/*Remove duplicate*/
for(i = 1; i<strings; i++)
{
if (!strcmp(str[i], str[pre_index]))
str[i][0] = '\0';
else
pre_index = i;
}
int ch[82], str_ch[82], no_word = 1;
for(i = 0; i<82; i++)
{
ch[i] = 0;
str_ch[i] = 0;
}
int x, y, j;
scanf("%d", &x);
scanf("%d", &y);
for(j = 0; j<x*y; j++)
{
char input;
scanf(" %c", &input);
ch[input-'A']++;
}
for (i = 0; i<strings; i++)
{
if (!strlen(str[i]))
continue;
for(j = 0; j<82; j++)
str_ch[j] = 0;
for (j = 0; j<strlen(str[i]); j++)
str_ch[str[i][j]-'A']++;
for(j = 0; j<82; j++)
if (str_ch[j] && str_ch[j] > ch[j])
break;
if (j == 82)
{
printf("%s ",str[i]);
no_word = 0;
}
}
if (no_word)
printf("-1");
printf("\n");
}
return 0;
}
- Problem Description
Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters.
Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell.
Example:
Input: dictionary[] = {“GEEKS”, “FOR”, “QUIZ”, “GO”};
boggle[][] = {{‘G’,’I’,’Z’},
{‘U’,’E’,’K’},
{‘Q’,’S’,’E’}};
Output: Following words of dictionary are present GEEKS, QUIZ
Input:
The first line of input contains an integer T denoting the no of test cases . Then T test cases follow. Each test case contains an integer x denoting the no of words in the dictionary.
Then in the next line are x space separated strings denoting the contents of the dictionary. In the next line are two integers N and M denoting the size of the boggle. The last line of each test case contains NxM space separated values of the boggle.
Output:
For each test case in a new line print the space separated sorted distinct words of the dictionary which could be formed from the boggle. If no word can be formed print -1.
Constraints:
1<=T<=10
1<=x<=10
1<=n,m<=7
- Test Case 1
Input (stdin)1
4
GEEKS FOR QUIZ GO
3 3
G I Z U E K Q S E
Expected OutputGEEKS QUIZ - Test Case 2
Input (stdin)1
4
SRM UNIV KTR CSE
3 3
U S N R V M I
Expected OutputSRM UNIV