Home » Technical Interview Questions » String Interview Questions » Recursive function to do substring search

Recursive function to do substring search


Reading Time - 2 mins

Given two strings s1 and s2, write a recursive function that returns TRUE if s2 is present in s1

Example

INPUT
s1 = “tutorial cup”
s2 = “cup”

OUTPUT
TRUE

Algorithm

1. If current character of s2 is last character of s1, but s2 has more characters then return FALSE

2. If current character of s1 is last character of s2 then return TRUE

3. If the characters match in s1 and s2, then check for the complete s2 in s1

4. If current characters dont match, then do recursive call for the remaining string.

C++ Program

#include<iostream>
using namespace std;
 
bool isExactMatch(char *s1, char *s2)
{
    if (*s1 == '\0' && *s2 != '\0')
        return false;
 
    // Else If last character of pattern reaches
    if (*s2 == '\0')
        return true;
 
    if (*s1 == *s2)
        return isExactMatch(s1 + 1, s2 + 1);
 
    return false;
}
 
// This function returns true if 's1' contain 's2'
bool isSubString(char *s1, char *s2)
{
    // If last character of s1 reaches
    if (*s1 == '\0')
        return false;

    // Else If last character of s2 reaches
    if (*s2 == '\0')
        return true;
 
    // If current characts of s2 and s1 match
    if (*s1 == *s2)
        return isExactMatch(s1, s2);
 
    // If current characts of s2 and s1 don't match
    return isSubString(s1 + 1, s2);
}
 
int main()
{
    char s1[] = "tutorial cup";
    char s2[] = "cup";
    if(isSubString(s1, s2))
    {
        cout<<"TRUE"<< endl;
    }
    else
    {
        cout<<"FALSE"<<endl;
    }
    return 0;
}

Try It

READ  String Compression

 

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions