Determine if characters of a String follows a specified order or not

Given a string and a pattern (having all distinct characters), determine if characters of the string follows specific order as defined by characters of the pattern.


 

For example,


Input: 
string = "Techie Delight"
pattern = "el";

Output: Pattern found

The characters of the pattern follows the order { e, e, e, l } in the input string. All e's appear before l.

 
Input: 
string = "Techie Delight"
pattern = "ei";

Output: Pattern not found

The characters of the pattern follows order { e, i, e, e, i } in the input string. All e's doesn't appear before all i's.

 


 

The idea is to loop through all characters of the pattern and if at any point, the last occurrence of previous encountered character is after the first occurrence of current character in the input string, we can say that the string doesn’t follow the order defined by the pattern.

C++

Download   Run Code

Output:

Pattern found

 
The time complexity of above solution is O(mn) where m is the length of the string and n is the length of the pattern.

 
Here’s another simple approach to solve this problem. The solution can be divided into three steps:

  1. Remove all characters from the given string that are not present in the specified pattern.
     
  2. Remove the adjacent duplicates from the modified string.
     
  3. Compare the resultant string with the pattern and return true if both are equal.

C++

Download   Run Code

Output:

Pattern not found

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz