// understanding the trinity (arrays, pointers, and memory allocation)

Previously, I've talked about the two types of parameter passing and introducing memory addresses, pointers, and the concept of referencing and dereferencing as a whole. However, this isn't the last time that we'll be seeing pointers. Pointers are an integral part of C programming, providing the programmer control with the variables that they create, and we'll be seeing it anywhere, including this post's topics: arrays and strings.

As a refresher, arrays are collections of objects of the same data type: ints, doubles, chars, etc. Strings on the other hand are arrays of characters. In C, there is no native string data type, so for the language to be able to distinguish that it is indeed a string and not just an array of characters, a null terminator or '\0' is added by the end.

What's interesting though is that despite the absence of a string data type, C still have a format specifier (%s) and built-in library (string.h) dedicated for strings, which I'll be talking about in this post.

With that said, let's jump in to the problem statement.

Problem

Implement a palindrome checker using various string functions in C.
Your program should be able to:

• Scan for the word to be checked
• Pass the word to a function called isPalindrome which returns an int to be interpreted in the main() whether the given word is a palindrome or not.
• Loop indefinitely until the word ”EXIT” is used as input.
• Store each palindrome in an array, then print all palindromes before exiting the program.

For this I'll be dividing the objectives into those who belong in the main and those who aren't. Quickly listing the initial variables, the only variable I need for now is just char[] string for the user input.

isPalidrome Function
Palidromes are words that reads the same backward or forward. This is the basis that I've used for my isPalindrome function. The goal was to reverse the string and store it on a different variable, then compare it to the original to see if it's the same.

There is another way to do this, which is by comparing the chars of the string from the beginning and from the end, meeting at the middle. However, the problem statement mentions that isPalindrome should be using the built-in string functions in C, so I'll be approaching using for the solution is by the definition.

As mentioned before, C has a built-in library made for strings called string.h. It contains various functions that deals with string operations such as strcpy to copy a string to a memory address and strcat to concatenate two strings. For this function, however, I'll only be using strlen to create the reverse string, and strcmp to compare the original string to its reverse.

Although it looks like the parameter of my function is the string itself, what's being passed is actually the pointer of the string. This is due to one property of arrays where calling an array without an index is the same as calling the pointer of its first element. Since the content of the array is stored sequentially in the memory, we can access all of the array just by incrementing said pointer. This is also important to point out as most string functions require the pointer that holds the string as the parameter.

int n1, n2;
int example[] = {1, 2, 3};

n1 = example[0];
n2 = *example; // Dereferencing example
printf("%d = %d", n1, n2); // 1 = 1

n1 = example[1];
n2 = *(example + 1); // Dereferencing example
printf("%d = %d", n1, n2); // 2 = 2

Going back to the function, to reverse the string, I first made a char array of len values called sReverse, where len is the length of the string obtained by strlen(string). From there, I set up a loop traversing through the original string, assigning each letter in the ((len - 1) - i)th index to the ith index of sReverse.

// String reversal
for (i = 0; i < len; i++) {
    sReverse[i] = string[len - i - 1];
}

However, this is not done yet as all I've done is make something like {'h', 'e', 'l', 'l', 'o'} instead of "hello" because of the missing null terminator at the end. This can be done by adding the following line:
sReverse[i] = '\0';

Now that I've done that, the only thing left to do is to compare the new sReverse string and the original string. If they are the same, the function returns 1 for true, and 0 otherwise. This part of the function is easily done by strcmp.

String Compare or strcmp takes two parameters and the way it works is by going through the strings character by character and comparing them by their values in the ASCII table. Here is the reference for strcmp:

The function strcmp() compares str1 and str2, then returns [a value]:

• less than 0 if str1 is less than str2
• equal to 0 if str1 is equal to str2
• greater than 0 if str1 is greater than str2

In this case though, all that matters is whether the string is equal or not, so I'll just be checking for if the output of strcmp is 0 or not.

This is the entirety of my isPalidrome function.

int isPalindrome(char string[]) {
    int len = strlen(string);
    char sReverse[len];
    int i;

    // String reversal
    for (i = 0; i < len; i++) {
        sReverse[i] = string[len - i - 1];
    }
    // Add a null-terminator at the end of the string
    sReverse[i] = '\0'; 

    // String comparison
    if (strcmp(string, sReverse) == 0) {
        return 1;
    } else {
        return 0;
    }
}

lowercase Function
Since isPalidrome uses strcmp (and by extension, ASCII values) to compare strings, strings that have both uppercase and lowercase letters such as "Level" or "huH" are immediately considered non-palindromes since uppercase letters have lower ASCII values than its lowercase counterparts. Therefore, I first need to standardize the inputs before passing them through isPalindrome.

Unfortunately, a built-in function that does this doesn't exist. Luckily, there's a library that deals with operations on characters itself, such as changing cases, or checking what the character is, and that is ctype.h.

lowercase is a utility function that I'll be using right before I call isPalindrome and all it does is exactly what it's called, change the case of the string to lowercase. I wanted to change the string itself instead of making a lowercase copy of the string, so I decided to use the pointer of the string to traverse it then individually use tolower(*i) where i is the pointer.

void lowercase(char* string) {
    char* i; // String pointer
    for (i = string; *i != '\0'; i++) {
        *i = tolower(*i);
    }
}

I stored the address of the string in i, and incremented it by one until it reaches the null terminator. This directly applies what I had mentioned earlier that arrays have its elements stored sequentially in the memory, so by doing i++, I am able to traverse the string.

main Function
Moving on to the main function, I went ahead and used a while loop with the terminating condition set to 1 so it would ask for input indefinitely, similar to what I already had done previously. In this case, I also added an if-else statement that would break the loop when the word EXIT is entered. All I needed to do was compare the user input to "EXIT" using strcmp. This is pretty much half of the main.

The next key thing that I needed to implement is to print all of the words that were determined to be a palindrome upon termination. This immediately told me to use arrays. One major obstacle, however, is that I don't know how many words the user is going to input since the input scanning runs indefinitely, and thus a fix-sized array will not work for this.

That said, there is another way of implementing arrays so long as the initial number of elements is known by dynamically allocating the array using malloc. In this case, I can set it to an arbitrary size and resize later on when the array is full. This is how to use malloc:

data_type ptr = malloc(initialSize * sizeof(data_type));

malloc returns a pointer of the data type indicated with the space requested calculated by sizeof(data_type) times the amount of elements that I want, similar to how the pointer of the array[0] works.

Another obstacle is that considering the array is storing strings, this array essentially becomes a multidimensional dynamically allocated array, which honestly sounds complicated, but in reality is pretty digestible. This diagram should help understand what's happening.

Therefore, the array is basically a pointer pointing to a pointer that is also pointing to a string. For this, I'll be making a char pointer array first,

int arraySize = 100;
char **array = malloc(arraySize * sizeof(char*));

and then set each element of that array to a dynamically allocated string.

int stringLength = 100;
array[i] = malloc((stringLength + 1) * sizeof(char));

Now that I have set that up, the last objective is to populate that array. Using strcpy, if isPalindrome determines that the user input is a palindrome, I can call strcpy to copy the user input into the array.

while (1) {
    // Scanning for user input

    if (strcmp(string, "EXIT") != 0) {
        lowercase(string);
        if (isPalindrome(string) == 1) {
            printf("%s is a Palidrome\n", string);

            // Storing the string
            array[i] = malloc((stringLength + 1) * sizeof(char)); 
            // +1 to account for the null-terminator
            strcpy(array[i], string); 
            // Copy the user string to the string address
            i++;
        } else {
            printf("%s is not a Palidrome\n", string);
        }
    } else {
        break;
    }
}

When the terminating condition is met, all I have to do is to loop through that array then print the elements. Finally, as always when dealing with dynamic allocation, I'll free up the 2D array by looping through the strings first, and then free the array itself.

Conclusion
Admittedly, this problem was pretty difficult especially with my almost non-existent understanding of how memory allocation works, added with the confusion once you lose track of where a pointer is pointing to.

The main issue for me was setting up the 2D array using malloc, primarily, because I can't internalize what happens when I dynamically allocate things. It only started to make sense once I had started breaking down the syntax itself, looking at what each parameter does, how do they relate to pointers and what purpose does the return value serve.

On the other hand, the arrays and strings itself as a concept was tolerable for me since I already have experience with it. But overall, with some fiddling and trying things until something sticks helped me sort of work out how to use pointers, arrays, and memory allocation the way I need it. I definitely see now how powerful these concepts are when used correctly.