Question Name:Word Boggle

#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

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro