Home » Interview coding problems/challenges

Match a pattern and String without using regular expressions

Match a pattern and String without using regular expressions: Here, we are going to learn to match a pattern and string without using regular expressions using backtracking algorithm. Submitted by Souvik Saha, on February 07, 2020

Description

This is a standard interview problem to match a pattern and string without using regular expressions using backtracking algorithm.

Problem statement

A string and a pattern are given to you. You have to match the pattern and string without using regular expression.

    Input:
    Test Case T.

    T no. of lines with the strings and patterns.
    
    E.g.
    3
    abcbbabc
    aba
    Includehelp
    aa
    GreenRedYellowRed
    GRYR
    
    Output:
    Print the character with their respectively representation.

Example

    T= 3

    Input:
    String  : abcbbabc
    Pattern: aba
    
    Output:
    a →  abc
    b →  bb
    
    Input:
    String  : Includehelp
    Pattern: aa
    
    Output:
    Matching not possible.
    
    Input:
    String  : GreenRedYellowRed
    Pattern: GRYR
    
    Output:
    G → Green
    R → Red
    Y → Yellow

Explanation with example

Match a string with a pattern is a problem of combination and we will solve this problem with the backtracking process.

To solve this problem, we will follow this algorithm,

match(string ,pattern ,string_pointer,patter_pointer,map,set):
    if(string_pointer equals to the null pointer of the string and 
    pattern_pointer equals to the null pointer of the pattern) Then
        return true
    end if
    if(string_pointer equals to the null pointer of the string or 
    pattern_pointer equals to the null pointer of the pattern) Then
        return false
    end if
    for i-> string_pointer+1 to string_length
        taking a substring of the original from string_pointer to i
        if(the substring is not in map)Then
            if(pattern is already present in the set) Then
                continue
            end if
            insert the pair of substring and the corresponding pattern into the map
            insert the pattern into the set
        end if
        else if(the substring is already map) Then
            if(substring's corresponding pattern is not matched with
            the pattern which is at the patter_pointer) Then
            continue;
            end if
        end if
        if(call the pattern for string_pointer+1 and patter_pointer+1)
            return true;
    end for
    return false;

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

bool match(string str, string pat, int str_pos, int pat_pos, map<string, char>& m, set<char>& se)
{
    if (str_pos == str.length() && pat_pos == pat.length()) {
        return true;
    }
    if (str_pos >= str.length() || pat_pos == pat.length())
        return false;
    int flag = 0;
    for (int i = str_pos + 1; i <= str.length(); i++) {
        string s = str.substr(str_pos, (i - str_pos));
        //if the substring is not present in the map
        if (m.find(s) == m.end()) {
            //if the pattern is already has a string
            if (se.find(pat[pat_pos]) != se.end())
                continue;
            m.insert(make_pair(s, pat[pat_pos]));
            se.insert(pat[pat_pos]);
            flag = 1;
        }
        //if the substring is already present into the map
        else if (m.find(s) != m.end()) {
            //if the corresponding pattern is not match with the current pattern
            if (m[s] != pat[pat_pos]) {
                continue;
            }
        }
        if (match(str, pat, i, pat_pos + 1, m, se))
            return true;
        if (flag) {
            m.erase(s);
            se.erase(pat[pat_pos]);
            flag = 0;
        }
    }
    return false;
}

void match_the_pattern(string str, string pat)
{
    map<string, char> m;
    int str_pos = 0;
    int pat_pos = 0;
    set<char> s;
    if (match(str, pat, str_pos, pat_pos, m, s)) {
        map<string, char>::iterator it;
        for (it = m.begin(); it != m.end(); it++) {
            cout << it->second << " -> " << it->first << endl;
        }
    }
    else {
        cout << "Matching not possible" << endl;
    }
}

int main()
{
    int t;

    cout << "Test Case : ";
    cin >> t;

    while (t--) {
        string str, pat;
        cout << "Enter the String : ";
        cin >> str;
        cout << "Enter the pattern : ";
        cin >> pat;
        match_the_pattern(str, pat);
    }

    return 0;
}

Output

Test Case : 3
Enter the String : abcbbabc
Enter the pattern : aba
a -> abc
b -> bb
Enter the String : includehelp
Enter the pattern : aa
Matching not possible
Enter the String : GreenRedYellowRed
Enter the pattern : GRYR
G -> Green
R -> Red
Y -> Yellow