CODEWITHSUNDEEP
javascripttypescriptecmascript-6
Manoj
Manoj

Reputation: 722

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

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.

Upvotes: 1

Views: 10327

Answers (6)

veerendranath darsi
veerendranath darsi

Reputation: 1

I have implemented the same in c#

class Program
{
    static void Main(string[] args)
    {
        //I took these to for an example but this works for any source and pattern 
        string source = "amazing";
        string pattern = "010";

        int diff = source.Length - pattern.Length;
        int count = 0;

        for (int i = 0; i <= source.Length; i++)
        {
            if (i <= diff)
            {
                count = count + CheckMatch(source.Substring(i, pattern.Length), pattern);
            }
        }
        Console.WriteLine("OverAll Count " + count);
        int CheckMatch(string subStr, string pattern)
        {
            string vowels = "aeiouy";
            List<bool> bools = new List<bool>();

            for (int i = 0; i < pattern.Length; i++)
            {
                //Console.WriteLine("pattren is " +  pattern[i] + " and subStrChar is " + subStr[i]);
                if (pattern[i] == '0' && vowels.Contains(subStr[i]) 
                    || pattern[i] == '1' && !vowels.Contains(subStr[i]))
                {
                    bools.Add(true);
                    //Console.WriteLine(true);
                }
                else
                {
                    bools.Add(false);
                    //Console.WriteLine(false);
                }
            }
            var count = bools.All(x => x) ? 1 : 0;
            return count;
        }
    }
}

Upvotes: 0

sivi
sivi

Reputation: 11114

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)

Upvotes: 0

Niang Moore
Niang Moore

Reputation: 506

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

Upvotes: 0

Tibebes. M
Tibebes. M

Reputation: 7558

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

Upvotes: 4

Ehsan Nazeri
Ehsan Nazeri

Reputation: 801

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" ]

Upvotes: 1

Nina Scholz
Nina Scholz

Reputation: 386670

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'));

Upvotes: 1

Related Questions