String Is Palindrome Or Not In C Without String Functions

In C programming, checking if a string is a palindrome without relying on built-in string functions like strlen, strcmp, or strrev requires a fundamental understanding of character arrays and manual iteration. In this article, you will learn how to implement robust palindrome checks using basic C constructs.

Problem Statement

A palindrome is a sequence of characters that reads the same forwards and backward. For example, "madam," "level," and "racecar" are palindromes. The challenge is to write a C program that determines if a user-input string is a palindrome, specifically prohibited from using standard library string manipulation functions. This often means manually calculating string length and comparing characters.

Example

Consider the following examples:

• Input: madam
• Output: madam is a palindrome.
• Input: hello
• Output: hello is not a palindrome.

Background & Knowledge Prerequisites

To understand and implement the solutions effectively, readers should be familiar with:

• C Basics: Variables, data types, operators.
• Arrays: Declaring and accessing elements, particularly character arrays (strings).
• Loops: for and while loops for iteration.
• Pointers: Basic understanding of pointer arithmetic (though not strictly required for the most basic approach, it's fundamental for C string manipulation).
• Standard I/O: Using printf for output and scanf or fgets for input. The example will use fgets for safer string input.
• Null Terminator: Understanding that C strings are null-terminated (\0).

Relevant Imports: All examples will require #include for input/output operations.

Use Cases or Case Studies

Checking for palindromes can be useful in various contexts:

• Algorithmic Challenges: Often posed as a basic coding interview question to assess a candidate's understanding of string manipulation and loops.
• Data Validation: In applications requiring specific text patterns, palindromes might serve as a unique identifier or validation rule (e.g., specific codes or sequences).
• Educational Tools: Demonstrating fundamental programming concepts like iteration, conditional logic, and array manipulation without relying on high-level library functions.
• Text Processing Games: Puzzles or games where identifying palindromic words or phrases is part of the gameplay.
• Bioinformatics: Although less common, similar pattern-matching logic can apply to identifying reverse complementary sequences in DNA strands, which share a conceptual similarity with palindromes.

Solution Approaches

Here, we will explore two distinct approaches to check for palindromes without using C's string functions.

Approach 1: Two-Pointer Iteration

This approach is highly efficient. It involves using two pointers (or indices): one starting at the beginning of the string and one at the end. These pointers move towards each other, comparing characters at each step.

• One-line summary: Iterate from both ends of the string towards the center, comparing characters.

// Palindrome Check using Two Pointers
#include <stdio.h>

// Function to manually calculate string length
int calculate_length(char* str) {
    int length = 0;
    while (str[length] != '\\0' && str[length] != '\\n') { // Account for newline from fgets
        length++;
    }
    return length;
}

// Function to check if a string is a palindrome
int is_palindrome_two_pointers(char* str) {
    int length = calculate_length(str);
    int start = 0;
    int end = length - 1;

    // Remove potential trailing newline if it's there
    if (length > 0 && str[end] == '\\n') {
        str[end] = '\\0'; // Replace newline with null terminator
        length--;        // Adjust length
        end--;
    }
    
    // If the string is empty or has one character, it's a palindrome
    if (length <= 1) {
        return 1; 
    }

    while (start < end) {
        if (str[start] != str[end]) {
            return 0; // Not a palindrome
        }
        start++;
        end--;
    }
    return 1; // It is a palindrome
}

int main() {
    char input_string[100]; // Buffer to store the input string

    // Step 1: Prompt user for input
    printf("Enter a string: ");
    
    // Step 2: Read string safely using fgets
    // fgets reads up to size-1 characters or until a newline, storing the newline
    if (fgets(input_string, sizeof(input_string), stdin) == NULL) {
        printf("Error reading input.\\n");
        return 1;
    }

    // Step 3: Check if it's a palindrome and print result
    if (is_palindrome_two_pointers(input_string)) {
        printf("'%s' is a palindrome.\\n", input_string);
    } else {
        printf("'%s' is not a palindrome.\\n", input_string);
    }

    return 0;
}

Run

• Sample Output:

  Enter a string: level
  'level' is a palindrome.
  
  Enter a string: programming
  'programming' is not a palindrome.
  
  Enter a string: A
  'A' is a palindrome.
  
  Enter a string:
  '' is a palindrome.

• Stepwise Explanation:

1. calculate_length(char* str): This helper function manually iterates through the string character by character until it encounters the null terminator (\0) or a newline character (\n) (which fgets often includes). It counts the number of characters and returns the length.
2. is_palindrome_two_pointers(char* str):
   • It first gets the effective length of the string using the calculate_length helper.

Approach 2: Manual Reversal and Comparison

This approach involves creating a reversed copy of the original string without using strrev and then comparing this reversed copy character by character with the original string.

• One-line summary: Create a new string by manually reversing the original, then compare it character by character with the original.

// Palindrome Check using Manual Reversal
#include <stdio.h>

// Function to manually calculate string length
int calculate_length(char* str) {
    int length = 0;
    while (str[length] != '\\0' && str[length] != '\\n') { // Account for newline from fgets
        length++;
    }
    return length;
}

// Function to check if a string is a palindrome by reversing it
int is_palindrome_manual_reverse(char* original_str) {
    char cleaned_str[100]; // To store the string without newline
    int clean_len = 0;

    // Step 1: Clean the string (remove newline) and calculate effective length
    int i = 0;
    while (original_str[i] != '\\0' && original_str[i] != '\\n') {
        cleaned_str[clean_len++] = original_str[i];
        i++;
    }
    cleaned_str[clean_len] = '\\0'; // Null-terminate the cleaned string

    // If the string is empty or has one character, it's a palindrome
    if (clean_len <= 1) {
        return 1;
    }

    char reversed_str[100]; // Buffer for the reversed string
    int j;

    // Step 2: Manually reverse the cleaned string
    for (j = 0; j < clean_len; j++) {
        reversed_str[j] = cleaned_str[clean_len - 1 - j];
    }
    reversed_str[clean_len] = '\\0'; // Null-terminate the reversed string

    // Step 3: Manually compare the original (cleaned) string with the reversed string
    for (j = 0; j < clean_len; j++) {
        if (cleaned_str[j] != reversed_str[j]) {
            return 0; // Not a palindrome
        }
    }
    return 1; // It is a palindrome
}

int main() {
    char input_string[100]; // Buffer to store the input string

    // Step 1: Prompt user for input
    printf("Enter a string: ");
    
    // Step 2: Read string safely using fgets
    if (fgets(input_string, sizeof(input_string), stdin) == NULL) {
        printf("Error reading input.\\n");
        return 1;
    }

    // Step 3: Check if it's a palindrome and print result
    if (is_palindrome_manual_reverse(input_string)) {
        // For printing, we need to handle the newline possibly in input_string
        int len = calculate_length(input_string);
        if (len > 0 && input_string[len] == '\\n') {
            input_string[len] = '\\0'; // Temporarily null-terminate for clean printing
        }
        printf("'%s' is a palindrome.\\n", input_string);
    } else {
        int len = calculate_length(input_string);
        if (len > 0 && input_string[len] == '\\n') {
            input_string[len] = '\\0';
        }
        printf("'%s' is not a palindrome.\\n", input_string);
    }

    return 0;
}

Run

• Sample Output:

  Enter a string: rotor
  'rotor' is a palindrome.
  
  Enter a string: example
  'example' is not a palindrome.

• Stepwise Explanation:

1. Cleaning the Input: The main function uses fgets which can include a newline. The is_palindrome_manual_reverse function first creates cleaned_str to store the input without the \n character and determines its clean_len.
2. calculate_length(char* str): Similar to the previous approach, this helper determines the effective length of the string without including the newline character.
3. Manual Reversal: A new character array, reversed_str, is created. A for loop iterates from 0 to clean_len - 1. In each iteration, the character from cleaned_str at clean_len - 1 - j (which corresponds to the character at the end of the original string, then second to last, etc.) is copied to reversed_str[j]. After the loop, reversed_str is null-terminated.
4. Manual Comparison: Another for loop iterates through both cleaned_str and reversed_str from j = 0 to clean_len - 1.
5. If, at any point, cleaned_str[j] does not equal reversed_str[j], the function returns 0 (false).
6. If the loop completes, it means all characters matched, and the function returns 1 (true).

Conclusion

Checking if a string is a palindrome without relying on C's standard string functions provides a valuable exercise in fundamental programming. Both the two-pointer approach and the manual reversal method demonstrate how to manage strings and compare characters directly. While the two-pointer method is generally more efficient as it avoids allocating extra memory for a reversed string, both approaches effectively solve the problem while adhering to the constraint of manual implementation.

Summary

• A palindrome reads the same forwards and backward.
• Checking without string functions requires manual length calculation and character comparisons.
• Two-Pointer Approach: Compares characters from both ends inward, stopping at the first mismatch or when pointers meet.
• Manual Reversal Approach: Creates a new, manually reversed copy of the string and then compares it character by character with the original.
• fgets is a safer way to get string input but often includes a newline character, which needs to be handled.
• Both methods rely on basic loops, array indexing, and conditional logic.