JavaScript - Dynamic RegExp for Duplicate Characters

user_14297151 0
Viewed 101

I'm very new to programming, and I'm trying to solve an exercise where you encode a string (in this case, a single word) based on whether or not the constituent characters occur twice or more. Characters occurring only once encode to, say "■", characters encoding twice or more encode to, say "X".

Example: input = "hippodrome" :: output = "■■XXX■■X■■"

I managed to solve it in a very convoluted way using nested loops and a key:value object storing character:occurrences, but i am trying to refactor the solution to be more efficient using a dynamically created RegExp, but i think i'm not understanding regex notation.

function encodeDupes(word) {
  let encoded = "";
  for (let char of word) {
    let regex = new RegExp(char + "{2,}","ig"); // create a regex to see if "char" occurs 2 or more times
    regex.test(word) ? encoded += "X" : encoded += "■"; // check this char against rest of word, push appropriately
  }
  return encoded;
}

it works with a more simple gate like char < "m" ? do X : do Y, and i thought i understood this answer here ({n,} = at least n occurrences), but i'm new enough that i'm still not sure if it's my regex or my logic.

thank you!

javascript regex
2 Answers

I'm very new to programming, ..., I am trying to refactor the solution to be more efficient using a dynamically created RegExp...

That's a bit of a catch 22 because regular expressions trade efficiency for convenience. In order for the regular expression "engine" to run, a grammar must be established, and a lexer, parser, and evaluator transform the string-based input expressions into program output. It's (sometimes) convenient to implement a particular program using regular expressions, but it's almost impossible to beat out a fundamental algorithm that isn't slowed down by the regular expression engine.

I managed to solve it in a very convoluted way using nested loops and a key:value object storing character:occurrences ...

Convoluted indeed, but sadly not uncommon to see even "expert" programmers do such things. An efficient algorithm emerges when we realise we don't need to count each letter. Instead, we only need to know whether a letter occurs more than once. Using two Set objects, once and more, we can determine the answer without needing to allocate counter memory per letter! And sets are lightning fast, thanks to O(1) constant-time lookup -

function encodeDupes(word)
{ const once = new Set
  const more = new Set
  
  for (const c of word)
    if (more.has(c))
      continue
    else if (once.has(c))
      (once.delete(c), more.add(c))
    else
      once.add(c)
      
  return Array
    .from(word, c => more.has(c) ? "X" : "■")
    .join("")
}

console.log(encodeDupes("hippodrome"))

Output

■■XXX■■X■■
user_6331830

Usually RegExp are used to compare entire words or phrases.

Whenever {n,} is used, it's searching for two or more characters consecutively. Here's an example:

n{2,}
nn     # match
anna   # match
nan    # does not match

The following RegExp isn't perfect, but it should suffice, replacing n with the character of your choice

(.*n{2,}.*)|(.*n.*n.*)+

(.*n{2,}.*) —— for consecutive ‘n’s 
|  —— or
(.*n.*n.*)+ —— ‘n’s with anything in between

Let me know how it goes.

user_141603090
Related