Home » Technical Interview Questions » String Interview Questions » Check if string follows order of characters by a pattern or not

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


Reading Time - 3 mins

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

 

READ  Valid Number
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions