Hispazn
Hispazn

Reputation: 103

How to check if a particular string in one array is in another array

I have an array called puzzle which consist of words/letters/random strings and I want to check if it has any of the same strings in another array called dictionary (the strings in dictionary are listed in alphabetical order)

So I believe my problem is the binary search in my program, I'm not entire sure how to work around it using strings. I tried to use some strcmp() but I don't think thats the way to go?

When the program runs, it gets no output. that there is no matches but there are.

here is my binary search function:

int binsearch(char **dictionary, char *puzzle) {
    int start = 1;  //excluded first string of dictionary array bc #
    int end = listlength;
    while (start < end) {
        int mid = (start + end) / 2;
        int temp = strcmp(dictionary[mid], puzzle);
        if (temp < 0) {
            start = mid + 1; //it is in upper half
        } else
        if (temp > 0) {  //check lower half
            end = mid;
        } else
            return 1; //found a match hopefully
    }
    return 0;
}

and my entire code is here if maybe something you need to see

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define listlength 149256
#define maxWordLen 19

char **getWords(int rows, int cols);
void freeArray(char **array, int rows);
char **makeGridArray(int rows, int cols);
int binsearch(char **dictionary, char *puzzle);
void wordSearch(char **dictionary, char **puzzle, int row, int col);
const int DX_SIZE = 8;
const int DX[] = { -1, -1, -1,  0,  0,  1,  1,  1 };
const int DY[] = { -1,  0,  1, -1,  1, -1,  0,  1 };

int main() {

    //read in dictionary
    int i, j, x = 0, numCases, gridRow, gridCol;
    char **words = getWords(listlength, maxWordLen);

    //Get number of cases.
    printf("enter number of cases:\n");
    scanf("%d", &numCases);

    //process each case.
    while (x < numCases) {
        scanf("%d%d", &gridRow, &gridCol);

        //make word search grid
        char **grid = makeGridArray(gridRow + 1, gridCol);

        /* for testing if grid is storing properly
        for (i = 0; i < gridRow + 1; i++) {
            printf("%s\n", grid[i]);
        }
        */

        printf("Words Found Grid #%d:\n", x + 1);
        wordSearch(words, grid, gridRow + 1, gridCol);
        x++;
        freeArray(grid, gridRow + 1);
    }
    freeArray(words, listlength);
}

char **getWords(int rows, int cols) {
    int i;

    //allocate top level of pointers.
    char **words = malloc(sizeof(char*) * rows);

    //allocate each individual array
    for (i = 0; i < rows; i++) {
        words[i] = malloc(sizeof(char) * cols + 1);
    }

    //read dictionary.txt
    FILE *dictionary = fopen("dictionary.txt", "r");
    for (i = 0; i < rows; i++) {
        fgets(words[i], cols + 1,dictionary);
    }
    fclose(dictionary);
    return words;
}

char **makeGridArray(int rows, int cols) {
    //allocate top level of pointers.
    char **grid = malloc(sizeof(char*) * rows);
    int i, j;

    //allocate each individual array
    for (i = 0; i < rows; i++) {
        grid[i] = malloc(sizeof(char) * cols + 1);
    }
    //read in user input grid
    for (i = 0; i < rows; i++) {
        gets(grid[i]);
    }
    return grid;
}

int binsearch(char **dictionary, char *puzzle) {
    int start = 1;  //excluded first string of dictionary array bc #
    int end = listlength;
    while (start < end) {
        int mid = (start + end) / 2;
        int temp = strcmp(dictionary[mid], puzzle);
        if (temp < 0) {
            start = mid + 1; //it is in upper half
        } else
        if (temp > 0) {  //check lower half
            end = mid;
        } else
            return 1; //found a match hopefully
    }
    return 0;
}

void wordSearch(char **dictionary, char **puzzle, int row, int col) {
    int i, X, Y, dir;
    char wordsfound[19] = { '\0' };
    for (X = 0; X < row + 1; X++) {
        for (Y = 0; Y < col; Y++) {
            for (dir = 0; dir < DX_SIZE; dir++) //check every direction
                for (i = 0; i < 19; i++) {
                    //will continue in direction DX,DY starting at x,y
                    int nextX = X + DX[dir] * i;
                    int nextY = Y + DY[dir] * i;
                    if (nextX < 0 || nextX >= row) break; //keep in bounds
                    if (nextY < 0 || nextY >= col) break;
                    //store the string of letters to check
                    wordsfound[i] = (puzzle[nextX][nextY]);
                    if (i > 3) { //minimum word is 4
                        wordsfound[i + 1] = '\0';
                        //if the string of letters is actually a word, print
                        int bin = binsearch(dictionary, wordsfound);
                        if (bin) {
                            printf("%s\n", wordsfound);
                        }
                    }
                }
        }
    }
    return;
}

void freeArray(char **array, int rows) {
    //free arrays
    int i;
    for (i = 0; i < rows; i++) {
        free(array[i]);
    }
    free(array);
}

Upvotes: 0

Views: 65

Answers (1)

chqrlie
chqrlie

Reputation: 144780

The problem is in the getwords() function: you read the words from the dictionary with fgets() but forget to remove the trailing \n. All words in the dictionary have a trailing \n, so none of them match your searches.

Here is a corrected version:

char **getWords(int rows, int cols) {
    char line[256];
    int i;

    //allocate top level of pointers.
    char **words = malloc(sizeof(char*) * rows);

    //read dictionary.txt
    FILE *dictionary = fopen("dictionary.txt", "r");
    for (i = 0; i < rows; i++) {
        if (!fgets(line, sizeof line, dictionary))
            line[0] = '\0';
        line[strcspn(line, "\n")] = '\0';
        words[i] = strdup(line);
    }
    fclose(dictionary);
    return words;
}

Note that it would be better not to rely on a known magical listlength. You could also ignore comment and empty lines while reading the dictionary.

Upvotes: 1

Related Questions