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

Given an input string and a pattern, check if characters in the input string follows the same order as determined by characters present in the pattern. Assume there won’t be any duplicate characters in the pattern.

Examples:

Input: string = "engineers rock", pattern = "er";
Output: true
All 'e' in the input string are before all 'r'.

Input: string = "engineers rock", pattern = "egr";
Output: false
There are two 'e' after 'g' in the input string.

Input: string = "engineers rock", pattern = "gsr";
Output: false
There are one 'r' before 's' in the input string.

Algorithm: The approach is quite simple. Please follow the below steps:

Step1: First get a new filtered string from input string that has same characters as pattern.

1.1. Loop over all the characters of the input string.
1.2. Check whether a input string’s character matches with any character of pattern.
1.3. If there are any consecutive characters then add only one character to our filtered list. To do so, use a char type variable and match it with current variable, if matches then skip otherwise add current character to our filtered list.

Step2: Filtered list has only same number of characters as our pattern, if not then return FASLE, if yes then match all the characters. If there is any character that doesn’t match in the same sequence as pattern then return false otherwise return TRUE.

We are done now. Lets see the actual implementation of the above algorithm.

class StringPatternMatching
{
  static void Main(string[] args)
  {
    Console.WriteLine(IsStringFollowThePattern("engineers rock", "er"));
    Console.WriteLine(IsStringFollowThePattern("engineers rock", "egr"));
    Console.WriteLine(IsStringFollowThePattern("engineers rock", "gsr"));
    Console.WriteLine(IsStringFollowThePattern("engineers rock", "eger"));
    Console.ReadKey();
  }
 
  static bool IsStringFollowThePattern(string input, string pattern)
  {
    var filteredInputCharacters = new List<char>();
    char previousChar = default(char);
    /// Loop over the input string to get only pattern matching 
    /// characters
    foreach (var item in input)
    {
      /// Check for the pattern characters, if match then go
      if (pattern.Contains(item))
      {
         /// If there are consecutive duplicate characters then add 
         /// only one, skip rest. If previous character is same as 
         /// current character then skip otherwise add it to our
         /// filtered list.
         if (previousChar != item)
         {
            filteredInputCharacters.Add(item);
            previousChar = item;
         }
       }
     }
 
     /// Filtered list has only same number of characters as our pattern, 
     /// if not then return FASLE, if yes then match all the characters.
     /// If there is any character that doesn't match in the same sequence 
     /// as pattern then return false otherwise return TRUE.
     for (int i = 0; i < filteredInputCharacters.Count; ++i)
     {
       if (filteredInputCharacters[i] != pattern[j])
       {
         return false;
       }
     }
 
     return true;
   }
}

 

 

 

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s