binary Pattern Matching in ES6 with (pattern, s) as strings

Question

Given two strings pattern and s. The first string pattern contains only the symbols 0 and 1, and the second string s contains only lowercase English letters.

Let's say that pattern matches a substring s[l..r] of s if the following 3 conditions are met:

1. they have equal length;
2. for each 0 in pattern the corresponding letter in the substring is a vowel;
3. for each 1 in pattern the corresponding letter is a consonant. the task is to calculate the number of substrings of s that match pattern.

Note: In this we define the vowels as a,e,i,o,u, and y. All other letters are consonants.

I am not challenging anyone here, I have tried different ways but could not achieve. This question was asked in codesignal test assessment recently.

Answer 1

Here is my approach to tackle the problem.

replacing all 0 to a regex matching vowels and 1 to non-vowels from the pattern (after checking the inputs) and using that as regex (with overlapping) on s can help us with the requirements set.

function matchOverlap(input, re) {
  var r = [],
    m;
  // prevent infinite loops
  if (!re.global) re = new RegExp(
    re.source, (re + '').split('/').pop() + 'g'
  );
  while (m = re.exec(input)) {
    re.lastIndex -= m[0].length - 1;
    r.push(m[0]);
  }
  return r;
}

function algorithm(pattern, s) {
  const VOWELS = 'aeiouy'

  if (pattern.match('[^01]'))
    throw new Error('only 0 and 1 allowed in pattern')
  else if (s.match('[^a-z]'))
    throw new Error('only a-z allowed in s')

  const generatedRegex = new RegExp(
    pattern
      .replace(/0/g, `[${VOWELS}]`)
      .replace(/1/g, `[^${VOWELS}]`),
    'g')

  console.log("GENERATED REGEX:", generatedRegex)

  const matches = matchOverlap(s, generatedRegex)
  console.log("MATCHES:", matches)
  return matches.length
}


console.log("FINAL RESULT: " + algorithm('101', 'wasistdas'))

// the following throws error as per the requirement
// console.log(algorithm('234234', 'sdfsdf'))
// console.log(algorithm('10101', 'ASDFDSFSD'))

The matchOverlap function used was taken from this answer

Answer 2

You could take check for length first and then check the test with a regular expression for consonants against the pattern and count.

function getCount(pattern, s) {
    if (pattern.length !== s.length) return false;
    const regExp = /^[^aeiouy]$/;
    let count = 0;
    
    for (let i = 0; i < pattern.length; i++) {
        if (+regExp.test(s[i]) === +pattern[i]) count++;
    }
    return count;
}

console.log(getCount('010', 'ama'));

Answer 3

you should convert the input string to binary format.

function convertToBinary(source) {
  var vowels = 'aeiouy'
  var len = source.length
  var binaryStr = ''
  for (i = 0; i < len; i++) {
    binaryStr += vowels.includes(source[i]) ? '0' : '1'
  }
  return binaryStr
}

function isMatch(txt, pattern) {
  return txt === pattern
}

function findMatches(source, pattern) {
  var binaryString = convertToBinary(source)
  var result = []
  var patternLen = pattern.length
  for (var i = 0; i < binaryString.length - patternLen; i++) {
    if (isMatch(binaryString.substr(i, patternLen), pattern)) {
      result.push(source.substr(i, patternLen))
    }
  }
  return result
}

var text = 'thisisaresultoffunction'
var pattern = '1011'

console.log(findMatches(text, pattern))

its result

[ "sult", "toff", "func" ]

Answer 4

This is a brute force C# version

int binaryPatternMatching(string pattern, string s) {
    int count = 0;
    char[] vowel = {'a', 'e', 'i', 'o', 'u', 'y'};
    for(int i=0; i<=(s.Length - pattern.Length); i++){
        int k=i;
        bool match = true;
        bool cTM = true;
        int j=0;
        
        while(match == true && j < pattern.Length){
            if(pattern[j] == '0')
            {
                if(vowel.Contains(s[k])){
                    cTM = true;
                }
                else{
                    cTM = false;
                }
            }
            else
            {
                if(!vowel.Contains(s[k])){
                    cTM = true;
                }
                else{
                    cTM = false;
                }
            }
            k += 1;
            j += 1;
            
            match = (match && cTM);
        }
        if(match){
            count += 1;
        }
    }
    return count;
}

can be optimized

Answer 5

got it! also look at this question

the regex lib is more powerful than re

import regex as re
   
def pattern_finder(pattern,source):
    
    vowels = ['aeouiy'] 

    # using list comprehension to build the regular expression
    reg_ex = "".join(['[aeiouy]' if num=='0' else '[^aeiouy]' for num in pattern ])
   
    #finding overlapped patterns
    matches = re.findall(reg_ex, source, overlapped=True)
   
    
    return len(matches)