Check if string follows order of characters by a pattern or not

Check if characters in the given input string follows the same order as determined by characters present in the given input pattern.

Examples

a) Input string : “programming”, pattern: “ra”
    Output : True
All r`s in the input string are before a. So, true

b) Input string : “programming”, pattern: “gra”
    Output : False
There is 2 r`s and a before g in input string. So, false

Time complexity : O(n)

Algorithm

1. Assign labels(numbers) to the characters of the pattern word.

2. Keep track of order of last visited character.

3. If label of current character is less than previous character, return false.

4. Else, update last label.

5. If it reaches the end it means all characters follow order, return true.

C++ Program

#include <bits/stdc++.h>

using namespace std;
 
bool CheckFollowPattern(string input_string, string pattern)
{
    //Initialize label vector with -1`s
    vector<int> label(256, -1);
    // Assign index according to characters in pattern
    int index = 1;
    for (int i = 0; i < pattern.length() ; i++)
    {
        label[pattern[i]] = index;
        index++;
    }
    //Store previous index
    //Check if string follow above inde
    int previous_index = -1;
    for (int i = 0; i < input_string.length(); i++)
    {
        if (label[input_string[i]] != -1)
        {
            if (label[input_string[i]] < previous_index)
            {
                return false;
            }
            //Next iteration
            previous_index =  label[input_string[i]];
        }
    }
    return true;
}
 
//Main function
int main()
{
    string input_string = "programming";
    string pattern = "ra";
    bool result;
    result = CheckFollowPattern(input_string, pattern);
    if (result==1)
    {
        cout<<"Output: True"<<endl;
    }
    else
    {
        cout<<"Output: False"<<endl;
    }
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top