Check if the given string follows the given pattern

Here is java backtracking solution. Source link.

public class Solution {

public boolean isMatch(String str, String pat) {
Map<Character, String> map = new HashMap<>();
return isMatch(str, 0, pat, 0, map);
 }

boolean isMatch(String str, int i, String pat, int j, Map<Character,  String> map) {
// base case
if (i == str.length() && j == pat.length()) return true;
if (i == str.length() || j == pat.length()) return false;

// get current pattern character
char c = pat.charAt(j);

// if the pattern character exists
if (map.containsKey(c)) {
  String s = map.get(c);

  // then check if we can use it to match str[i...i+s.length()]
  if (i + s.length() > str.length() || !str.substring(i, i + s.length()).equals(s)) {
    return false;
  }

  // if it can match, great, continue to match the rest
  return isMatch(str, i + s.length(), pat, j + 1, map);
}

// pattern character does not exist in the map
for (int k = i; k < str.length(); k++) {
  // create or update the map
  map.put(c, str.substring(i, k + 1));

  // continue to match the rest
  if (isMatch(str, k + 1, pat, j + 1, map)) {
    return true;
  }
}

// we've tried our best but still no luck
map.remove(c);

return false;
 }

}

Don't you just need to translate the pattern to a regexp using backreferences, i.e. something like this (Python 3 with the "re" module loaded):

>>> print(re.match('(.+)(.+)\\2\\1', 'catdogdogcat'))
<_sre.SRE_Match object; span=(0, 12), match='catdogdogcat'>

>>> print(re.match('(.+)(.+)\\1\\2', 'redblueredblue'))
<_sre.SRE_Match object; span=(0, 14), match='redblueredblue'>

>>> print(re.match('(.+)(.+)\\2\\1', 'redblueredblue'))
None

The regexp looks pretty trivial to generate. If you need to support more than 9 backrefs, you can use named groups - see the Python regexp docs.

The simplest solution that I can think of is to divide the given string into four parts and compare the individual parts. You don't know how long a or b is, but both as are of the same length as well as bs are. So the number of ways how to divide the given string is not very large.

Example: pattern = [a b a b], given string = redblueredblue (14 characters in total)

1. |a| (length of a) = 1, then that makes 2 characters for as and 12 characters is left for bs, i.e. |b| = 6. Divided string = r edblue r edblue. Whoa, this matches right away!
2. (just out of curiosity) |a| = 2, |b| = 5 -> divided string = re dblue re dblue -> match

Example 2: pattern = [a b a b], string = redbluebluered (14 characters in total)

1. |a| = 1, |b| = 6 -> divided string = r edblue b luered -> no match
2. |a| = 2, |b| = 5 -> divided string = re dblue bl uered -> no match
3. |a| = 3, |b| = 4 -> divided string = red blue blu ered -> no match

The rest is not needed to be checked because if you switched a for b and vice versa, the situation is identical.

What is the pattern that has [a b c a b c] ?