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

Check if string follows order of characters defined by a pattern or not - GeeksforGeeks
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.

For every pair (x, y) of consecutive characters in the pattern string, we find the last occurrence of x and first occurrence of y in the input string. If last occurrence of character x is after first occurrence of character y for any pair, we return false. Checking for every pair of consecutive characters in the pattern string will suffice. For example, if we consider three consecutive characters in the pattern say x, y and z, if (x, y) and (y, z) returns true, that implies (x, z) is also true.

bool checkPattern(string str, string pattern)

{

    // len stores length of the given pattern

    int len = pattern.length();

      

    // if length of pattern is more than length of

    // input string, return false;

    if (str.length() < len)

        return false;

      

    for (int i = 0; i < len - 1; i++)

    {

        // x, y are two adjacent characters in pattern

        char x = pattern[i];

        char y = pattern[i + 1];

         

        // find index of last occurrence of character x

        // in the input string

        size_t last = str.find_last_of(x);

          

        // find index of first occurrence of character y

        // in the input string

        size_t first = str.find_first_of(y);

          

        // return false if x or y are not present in the

        // input string OR last occurrence of x is after

        // the first occurrence of y in the input string

        if (last == string::npos || first == 

            string::npos || last > first)   

        return false;

    }

      

    // return true if string matches the pattern

    return true;

}

http://www.geeksforgeeks.org/check-if-string-follows-order-of-characters-defined-by-a-pattern-or-not-set-2/

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.

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).

    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;

    }

http://www.geeksforgeeks.org/check-if-string-follows-order-of-characters-defined-by-a-pattern-or-not-set-3/

In this approach we first assign a label (or order) to characters of pattern. The labels are assigned in increasing order.

For example, the pattern “gsr” is labeled as following

"g" => 1
"s" => 2
"r" => 3

It means ‘g’ will come first, then ‘s’, then ‘r’

After assigning labels to pattern characters, we iterate through string characters. While traversing, we keep track of label (or order) of last visited character. If label of current character is less than previous character, we return false. Otherwise we update last label. If all characters follow order, we return true.

bool checkPattern(string str, string pat)

{

    // Initialize all orders as -1

    vector<int> label(CHAR_SIZE, -1);

 

    // Assign an order to pattern characters

    // according to their appearance in pattern

    int order = 1;

    for (int i = 0; i < pat.length() ; i++)

    {

        // give the pattern characters order

        label[pat[i]] = order;

 

        // increment the order

        order++;

    }

 

    //  Now one by check if string characters

    // follow above order

    int last_order = -1;

    for (int i = 0; i < str.length(); i++)

    {

        if (label[str[i]] != -1)

        {

            // If order of this character is less

            // than order of previous, return false.

            if (label[str[i]] < last_order)

                return false;

 

            // Update last_order for next iteration

            last_order =  label[str[i]];

        }

    }

 

    // return that str followed pat

    return true;

}

Read full article from Check if string follows order of characters defined by a pattern or not - GeeksforGeeks