I am able to pass all of check50 except "handles most basic words properly"
https://cs50.me/checks/32244a2a71079c81f6b1dc1275aaf305b3f0149f
When I run ./speller texts/lalaland.txt in the terminal window to compare my solution with the staff's solution, I get an abnormal amount of misspelled words!
Staff solution
WORDS MISSPELLED: 955
WORDS IN DICTIONARY: 143091
WORDS IN TEXT: 17756
TIME IN load: 0.24
TIME IN check: 0.01
TIME IN size: 0.00
TIME IN unload: 0.02
TIME IN TOTAL: 0.27
My solution
WORDS MISSPELLED: 17187
WORDS IN DICTIONARY: 143091
WORDS IN TEXT: 17756
TIME IN load: 5.59
TIME IN check: 0.43
TIME IN size: 0.00
TIME IN unload: 15.96
TIME IN TOTAL: 21.98
My trie program
// Implements a dictionary's functionality
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "dictionary.h"
typedef struct trie
{
// Store current char in dictionary
bool is_word;
// 27 Pointers to the struct
struct trie *paths[27];
}
trie;
// Function prototypes
trie *createNode(void);
void freeNode(trie *temp);
// Global variables
// Declare global variable for root and trav of trie data structure and loaded bool for keeping track of dict
trie *root = NULL;
trie *trav = NULL;
int wordCounter = 0;
bool loaded = false;
// Returns true if word is in dictionary else false
bool check(const char *word)
{
// Make a new copy of word for changing word to lowercase
char wordCpy[strlen(word)];
strcpy(wordCpy, word);
// Set trav to point to root
trav = root;
// Set up index for each char in word
int trieIndex;
// Loop over each char in word given, moving through trie
for (int h = 0; h < strlen(wordCpy); h++)
{
// Make word given case-insensitive, using tolower function
wordCpy[h] = tolower(wordCpy[h]);
// Use trav pointer to move through respective index
if (wordCpy[h] == '\'')
{
trieIndex = 26;
}
else
{
trieIndex = wordCpy[h] - 'a';
}
// If trav pointer's next path location is NULL, word does not exist in trie
if (trav -> paths[trieIndex] == NULL)
{
return false;
}
// Move to next trie struct
trav = trav -> paths[trieIndex];
// For last char in word
if (trav -> is_word == true && h == strlen(wordCpy) - 1)
{
return true;
}
}
return false;
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
// Create root node for trie
root = createNode();
if (root == NULL)
{
return false;
}
// Create trie index for inserting char from words found in dictionary
int trieIndex;
// Create traversal pointer
trav = root;
// Open the dictionary file given
FILE *dictionaryPtr = fopen(dictionary, "r");
// Check if dictionary file could be opened
if (dictionaryPtr == NULL)
{
return false;
}
// Declare character to store each character of dictionary
char c;
// Declare an char array in order to store words found, LENGTH + 1 elements
char word[46];
memset(&word[0], 0, sizeof(word));
// Declare a char variable used in the process of adding word to trie
char charAdd;
// Declare an index for words found in dictionary
int index = 0;
// Loop over words in dictionary, add them to trie
for (c = fgetc(dictionaryPtr); c != EOF; c = fgetc(dictionaryPtr))
{
// If c contains newline character, indicates that new word is on next line
if (c == '\n')
{
// Add word into trie by looping over word
for (int i = 0; i < strlen(word); i++)
{
// Store each char of word into charAdd
charAdd = word[i];
// Get number to be added to root array path based on character
if (charAdd == '\'')
{
// If charAdd is an ', make trieIndex become last element in trie path index
trieIndex = 26;
// Add charAdd into trie, if charAdd exists, move trav pointer
if (trav -> paths[trieIndex] == NULL)
{
// Create new trie node at that index
trav -> paths[trieIndex] = createNode();
// If createNode() returned NULL, it has failed
if (trav -> paths[trieIndex] == NULL)
{
return false;
}
// Move trav pointer to new node
trav = trav -> paths[trieIndex];
}
else
{
// Move trav to next path
trav = trav -> paths[trieIndex];
}
}
else
{
// Get index value of char based on http://www.asciichart.com/
trieIndex = charAdd - 'a';
// Add charAdd into trie, if charAdd exists, move trav pointer
if (trav -> paths[trieIndex] == NULL)
{
trav -> paths[trieIndex] = createNode();
// If createNode() returned NULL, it has failed
if (trav -> paths[trieIndex] == NULL)
{
return false;
}
// Move trav pointer to correct index
trav = trav -> paths[trieIndex];
}
else
{
trav = trav -> paths[trieIndex];
}
}
}
// Set index back to 0 for the next word
index = 0;
// Set is_word bool in current node to true
trav -> is_word = true;
// Increment wordCounter by 1
wordCounter++;
// Set trav back to root for next word
trav = root;
}
else
{
// Add char c into word array and increment index by 1
word[index] = c;
index++;
}
}
// Close dictionary pointer
fclose(dictionaryPtr);
loaded = true;
// Return true if loading is successful
return true;
}
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
if (loaded == true)
{
return wordCounter;
}
else
{
return 0;
}
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
freeNode(root);
return true;
}
// Function used to create a new node for trie data structure
trie *createNode(void)
{
trie *node = malloc(sizeof(trie));
if (node == NULL)
{
return NULL;
}
// Loop over node trie struct and allocate all pointers in trie to NULL
for (int x = 0; x < 27; x++)
{
node -> paths[x] = NULL;
}
// Set is_word in node to false
node -> is_word = false;
return node;
}
void freeNode(trie *temp)
{
// Use of recursion to free up nodes
// If all of paths[27] are NULL, free node
for (int x = 0; x < 27; x++)
{
if (temp -> paths[x] != NULL)
{
freeNode(temp -> paths[x]);
}
}
free(temp);
}
Any help on how to solve this problem will be greatly appreciated! Thank You!
