Finding a Needle in a Haystack(Subset) using C

Published in

hackgenius

5 min readJun 19, 2020

Ever heard of a word strenuosity ? Well finding a needle in a haystack can be one strenuous work

Searching for a needle in a haystack and are at your wits end 😔? Then you have come to the right place. Well, this problem might be confusing😕, difficult😫or impossible😱 for you. Unless you understand the concept for pointer and recursion.

For some pointer is like an alien 👽 object which is incomprehensible. But pointers in C are easy and fun to learn. Some C programming tasks are performed more easily with pointers, and other tasks, such as dynamic memory allocation, cannot be performed without using pointers. So it becomes necessary to learn pointers to become a perfect C programmer.

What are Pointers?

A pointer is a variable whose value is the address of another variable, i.e., direct address of the memory location. Like any variable or constant, you must declare a pointer before using it to store any variable address.
It’s general form is:

type *var-name; //type is the pointer's base type and var-name is  
                //the variable name

It’s not that no one knows how to teach about pointers. It is not that no one can understand pointers or that you need a separate brain part to understand pointer. It all comes down to one's way of understanding it, or how much they truly want to learn pointers. One’s conviction to learn is something which determines if he/she as the ability to learn something or not.

As our coding mentors says: “It all comes down to perfect practice and effort.”

Let’s move on to the coding

Problem: There are two strings needle and haystack (or hay). You need to check if all the characters in the needle are present in haystack or not. If yes then return True (1) or False (0)

We can solve this problem in three ways. They all are similar in a sense but there is a significant difference and they are :

Non-recursive method using string functions.
Non-recursive method without using string function.
Recursive method.

1. Non-recursive method using string functions :

The non-recursive method is quite simple. We are using a single while loop and strchr function.

Let’s start by creating a function, which takes two strings as parameters. Let’s name it as subset_str , as string function is being used. Let the return type be int as we are returning 0(False) or 1(True)

int subset_str(const char *needle, const char *hay){
    return 1;
}

Our first test case will be to check whether hay is null. If yes then return 0.

int subset_str(const char *needle, const char *hay){
    if(!hay)
        return 0;
    return 1;
}

Next step is the code where we actually check for the needle.

int subset_str(const char *needle, const char *hay){
    if(!hay)
        return 0;
    while(*needle){
        if(!strchr(hay, *needle)) //search for the character 
                                  //in haystack and returns      
                                  //zero if not found
            return 0;
        needle++;     // if found increment needle to the next 
                      //character
    }
    return 1; //control will reach this point only when all the 
              //characters in needle were present in haystack so 
              //return 1
}

Let’s visualize this code using Python Tutor

2. Non-recursive method without using string function:

The second non-recursive method doesn’t need any string function, though the size of the code increases.

Let’s again start by creating a function, which takes two strings as parameters. Let’s name it as subset. And the return type is int.

int subset(const char *needle, const char *hay){
    return 1;
}

Again our First test case will be to check whether hay is null. If yes then return 0.

int subset(const char *needle, const char *hay){
    if(!hay && !*hay)
        return 0;
    return 1;
}

Next, we’ll check if all the characters of the needle are present in hay or not using a do-while loop.
We’ll use a variable start so that when the character is found in hay we can bring it back to the start of the string.

int subset(const char *needle, const char *hay){
    if(!hay)
        return 0;
    do{
       if{*needle && *needle == *hay){ /*if there is a character in
                                         needle and that character 
                                         is present in hay then */
          needle++, hay = start;       /*needle will be incremented 
                                         to the next character and 
                                         hay will be brought back to
                                         the start of the string*/
           
       }
    } while(*hay++);  // this loop will run till all the characters 
                     // of needle are found or all the character of
                     // hay are checked
    return !needle;
}

Let’s visualize this code using Python Tutor

3. Recursive method :

The third and last method is the recursive method. This method is like all two other methods. We will name it as subset_rec.

Like the earlier two, we will start off by checking for hay.

int subset_rec(const char *needle, const char *hay){
    if(!hay){
        return 0;
    }
}

Next, we will check if the characters of needle are present in hay or not.

int subset_rec(const char *needle, const char *hay){
    int start = hay;
    if(!hay){
        return 0;s
    }    do {
        if ( *needle && *needle == *hay){/*if there is a character
                                           in needle and that      
                                           character is present in 
                                           hay then increment needle
                                           to next character*/
            needle++;
            return subset_rec(needle,start);/*and return needle and 
                                           hay(back from first    
                                          character) to subset_rec*/
        }
            
    } while(*hay++);
    
    return !*needle;
}

Let’s visualize the code using python Tutor

Lastly, I would like to thank my coding mentors at KGiSL Institute of Technology (KiTE) who encouraged me to put out this successful attempt at solving this problem and also for teaching me the fundamentals that were required to solve this.