## Sunday, August 7, 2016

### 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