Check if string follows order of characters defined by a pattern or not | Set 2

0 0 7 minutes read

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.
Another solution to the same problem is posted here.
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.

The idea here is to reduce the given string to the pattern given. For characters given in the pattern, we only keep the corresponding characters in the string. In the new string, we delete continuous repeated characters. The modified string should then be equal to the pattern given. Lastly, we compare modified string to the pattern given and return true of false accordingly.
Illustration:

str = "bfbaeadeacc", pat[] = "bac"

1) Remove extra characters from str (characters
  that are not present in pat[]
str = "bbaaacc"   [f, e and d are removed]

3) Removed consecutive repeating occurrences of 
   characters
str = "bac"   

4) Since str is same as pat[], we return true

Below is implementation of above steps.

C++

// C++ code for the above approach
 
#include <iostream>
#include <unordered_set>
using namespace std;
 
bool followsPattern(string str, string pattern) {
 
  // Insert all characters of pattern in a hash set
  unordered_set<char> patternSet;
  for (int i = 0; i < pattern.length(); i++) {
    patternSet.insert(pattern[i]);
  }
 
  // Build modified string (string with characters only from pattern are taken)
  string modifiedStr = str;
  for (int i = str.length() - 1; i >= 0; i--) {
    if (patternSet.find(str[i]) == patternSet.end()) {
      modifiedStr.erase(i, 1);
    }
  }
 
  // Remove more than one consecutive occurrences of pattern characters from modified string
  for (int i = modifiedStr.length() - 1; i > 0; i--) {
    if (modifiedStr[i] == modifiedStr[i - 1]) {
      modifiedStr.erase(i, 1);
    }
  }
 
  // After above modifications, the length of modified string must be same as pattern length
  if (pattern.length() != modifiedStr.length()) {
    return false;
  }
 
  // And pattern characters must also be same as modified string characters
  for (int i = 0; i < pattern.length(); i++) {
    if (pattern[i] != modifiedStr[i]) {
      return false;
    }
  }
  return true;
}
 
int main() {
  string str = "engineers rock";
  string pattern = "er";
  cout << "Expected: true, Actual: " << followsPattern(str, pattern) << endl;
 
  str = "engineers rock";
  pattern = "egr";
  cout << "Expected: false, Actual: " << followsPattern(str, pattern) << endl;
 
  str = "engineers rock";
  pattern = "gsr";
  cout << "Expected: false, Actual: " << followsPattern(str, pattern) << endl;
 
  str = "engineers rock";
  pattern = "eger";
  cout << "Expected: true, Actual: " << followsPattern(str, pattern) << endl;
 
  return 0;
}
 
// This code is contributed by adityashatmfh

Java

// Java program to check if characters of a string follow
// pattern defined by given pattern.
import java.util.*;
 
public class OrderOfCharactersForPattern
{
    public static boolean followsPattern(String str, String pattern)
    {
        // Insert all characters of pattern in a hash set,
        Set<Character> patternSet = neHashSet<>();
        for (int i=0; i<pattern.length(); i++)
            patternSet.add(pattern.charAt(i));
 
        // Build modified string (string with characters only from
        // pattern are taken)
        StringBuilder modifiedString = new StringBuilder(str);
        for (int i=str.length()-1; i>=0; i--)
            if (!patternSet.contains(modifiedString.charAt(i)))
                modifiedString.deleteCharAt(i);
 
        // Remove more than one consecutive occurrences of pattern
        // characters from modified string.
        for (int i=modifiedString.length()-1; i>0; i--)
            if (modifiedString.charAt(i) == modifiedString.charAt(i-1))
                modifiedString.deleteCharAt(i);
 
        // After above modifications, the length of modified string
        // must be same as pattern length
        if (pattern.length() != modifiedString.length())
            return false;
 
        // And pattern characters must also be same as modified string
        // characters
        for (int i=0; i<pattern.length(); i++)
            if (pattern.charAt(i) != modifiedString.charAt(i))
                return false;
 
        return true;
    }
 
    // Driver program
    int main()
    {
        String str = "engineers rock";
        String pattern = "er";
        System.out.println("Expected: true, Actual: " +
                           followsPattern(str, pattern));
 
        str = "engineers rock";
        pattern = "egr";
        System.out.println("Expected: false, Actual: " +
                          followsPattern(str, pattern));
 
        str = "engineers rock";
        pattern = "gsr";
        System.out.println("Expected: false, Actual: " +
                           followsPattern(str, pattern));
 
        str = "engineers rock";
        pattern = "eger";
        System.out.println("Expected: true, Actual: " +
                           followsPattern(str, pattern));
 
        return 0;
    }
}

Python3

# Python3 program to check if characters of 
# a string follow pattern defined by given pattern.
def followsPattern(string, pattern):
 
    # Insert all characters of pattern in a hash set,
    patternSet = set()
 
    for i in range(len(pattern)):
        patternSet.add(pattern[i])
 
    # Build modified string (string with characters 
    # only from pattern are taken)
    modifiedString = string
    for i in range(len(string) - 1, -1, -1):
        if not modifiedString[i] in patternSet:
            modifiedString = modifiedString[:i] + \
                             modifiedString[i + 1:]
 
    # Remove more than one consecutive occurrences 
    # of pattern characters from modified string.
    for i in range(len(modifiedString) - 1, 0, -1):
        if modifiedString[i] == modifiedString[i - 1]:
            modifiedString = modifiedString[:i] + \
                             modifiedString[i + 1:]
 
    # After above modifications, the length of 
    # modified string must be same as pattern length
    if len(pattern) != len(modifiedString):
        return False
 
    # And pattern characters must also be same 
    # as modified string characters
    for i in range(len(pattern)):
        if pattern[i] != modifiedString[i]:
            return False
    return True
 
# Driver Code
if __name__ == "__main__":
    string = "engineers rock"
    pattern = "er"
    print("Expected: true, Actual:", 
           followsPattern(string, pattern))
 
    string = "engineers rock"
    pattern = "egr"
    print("Expected: false, Actual:", 
           followsPattern(string, pattern))
 
    string = "engineers rock"
    pattern = "gsr"
    print("Expected: false, Actual:", 
           followsPattern(string, pattern))
 
    string = "engineers rock"
    pattern = "eger"
    print("Expected: true, Actual:", 
           followsPattern(string, pattern))
 
# This code is contributed by
# sanjeev2552

C#

// C# program to check if characters of a string follow
// pattern defined by given pattern.
using System;
using System.Collections.Generic;
using System.Text;
 
class GFG
{
    public static bool followsPattern(String str, String pattern)
    {
        // Insert all characters of pattern in a hash set,
        HashSet<char> patternSet = new HashSet<char>();
        for (int i = 0; i < pattern.Length; i++)
            patternSet.Add(pattern[i]);
 
        // Build modified string (string with characters 
        // only from pattern are taken)
        StringBuilder modifiedString = new StringBuilder(str);
        for (int i = str.Length - 1; i >= 0; i--)
            if (!patternSet.Contains(modifiedString[i]))
                modifiedString.Remove(i, 1);
 
        // Remove more than one consecutive occurrences of pattern
        // characters from modified string.
        for (int i = modifiedString.Length - 1; i > 0; i--)
            if (modifiedString[i] == modifiedString[i - 1])
                modifiedString.Remove(i, 1);
 
        // After above modifications, the length of modified string
        // must be same as pattern length
        if (pattern.Length != modifiedString.Length)
            return false;
 
        // And pattern characters must also be same 
        // as modified string characters
        for (int i = 0; i < pattern.Length; i++)
            if (pattern[i] != modifiedString[i])
                return false;
 
        return true;
    }
 
    // Driver program
    public static void Main(String[] args)
    {
        String str = "engineers rock";
        String pattern = "er";
        Console.WriteLine("Expected: true, Actual: " +
                        followsPattern(str, pattern));
 
        str = "engineers rock";
        pattern = "egr";
        Console.WriteLine("Expected: false, Actual: " +
                        followsPattern(str, pattern));
 
        str = "engineers rock";
        pattern = "gsr";
        Console.WriteLine("Expected: false, Actual: " +
                        followsPattern(str, pattern));
 
        str = "engineers rock";
        pattern = "eger";
        Console.WriteLine("Expected: true, Actual: " +
                        followsPattern(str, pattern));
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript program to check if characters of a string follow
// pattern defined by given pattern.
 
function followsPattern(str, pattern)
{
    // Insert all characters of pattern in a hash set,
        let patternSet = new Set();
        for (let i=0; i<pattern.length; i++)
            patternSet.add(pattern[i]);
   
        // Build modified string (string with characters only from
        // pattern are taken)
        let modifiedString = (str).split("");
        for (let i=str.length-1; i>=0; i--)
            if (!patternSet.has(modifiedString[i]))
                modifiedString.splice(i,1);
   
        // Remove more than one consecutive occurrences of pattern
        // characters from modified string.
        for (let i=modifiedString.length-1; i>0; i--)
            if (modifiedString[i] == modifiedString[i-1])
                modifiedString.splice(i,1);
   
        // After above modifications, the length of modified string
        // must be same as pattern length
        if (pattern.length != modifiedString.length)
            return false;
   
        // And pattern characters must also be same as modified string
        // characters
        for (let i=0; i<pattern.length; i++)
            if (pattern[i] != modifiedString[i])
                return false;
   
        return true;
}
 
// Driver program
let str = "engineers rock";
let pattern = "er";
document.write("Expected: true, Actual: " +
                   followsPattern(str, pattern)+"<br>");
 
str = "engineers rock";
pattern = "egr";
document.write("Expected: false, Actual: " +
                   followsPattern(str, pattern)+"<br>");
 
str = "engineers rock";
pattern = "gsr";
document.write("Expected: false, Actual: " +
                   followsPattern(str, pattern)+"<br>");
 
str = "engineers rock";
pattern = "eger";
document.write("Expected: true, Actual: " +
                   followsPattern(str, pattern)+"<br>");
 
// This code is contributed by rag2127
</script>

Output:

Expected: true, Actual: true
Expected: false, Actual: false
Expected: false, Actual: false
Expected: true, Actual: true

Time Complexity: Time complexity of above implementations is actually O(mn + n^2) as we use deleteCharAt() to remove characters. We can optimize above solution to work in linear time. Instead of using deleteCharAr(), we can create an empty string and add only required characters to it.
StringBuilder is used to operate on input string. This is because StringBuilder is mutable, while String is immutable object. To create a new string takes O(n) space, so extra space is O(n).
We have discussed two more approaches to solve this problem.
Check if string follows order of characters defined by a pattern or not | Set 1
Check if string follows order of characters defined by a pattern or not | Set 3
This article is contributed by Lalit Ramesh Sirsikar. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!